—冒泡排序—
重复地走访要排序的数列，依次比较两个元素。顺序错误则交换顺序，否则不改变原先顺序。
算法描述
具体算法描述如下：
- <1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- <2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- <3>.针对所有的元素重复以上的步骤，除了最后一个；
- <4>.重复步骤1~3，直到排序完成。
代码实现
常规冒泡排序
// 常规冒泡排序
void Bubble_Sort(int a[], int n) // (数组，数组长度)
{
//外层循环(趟数) 最后一个元素已经有序 故 n-1
for (int i = 0; i < n - 1; ++i)
{ //内层循环，最后一个元素已经有序且每次向右移动进行比较 故 n-1-i
for (int j = 0; j < n - 1 - i; ++j)
{ // 升序
if (a[j] > a[j + 1]) // 如果前个元素比后后面一个元素大
{
int temp = a[j]; // 交换元素
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
改进版冒泡排序
改进冒泡排序： 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
耗时会比常规冒泡排序少一些.
// 改进版冒泡排序
void Bubble_sort(int a[],int n)
{
int i = n - 1; //初始时,最后位置保持不变
while (i > 0) {
int pos = 0; //每趟开始时,无记录交换
for (int j = 0; j < i; j++)
if (a[j] > a[j + 1]) {
pos = j; //记录交换的位置
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
i = pos; //为下一趟排序作准备
}
}
算法分析
平均情况：T(n) = O(n2)
最佳情况：T(n) = O(n)
当输入的数据已经是正序时
- 最差情况：T(n) = O(n2)
当输入的数据是反序时
稳定性
- 稳定
若相邻元素相等，则不交换两元素位置，故稳定。
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
