7.6 交换排序——冒泡排序

交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

冒泡排序概念

冒泡排序便是交换排序的一种。

冒泡排序的思想（忘了从哪本书摘抄的了，凑合着看吧）

例如有6个元素需要排序：
6 5 3 4 1 2
第1轮：

[5 6] 3 4 1 2
5 [3 6] 4 1 2
5 3 [4 6] 1 2
5 3 4 [1 6] 2
5 3 4 1 [2 6]//第1轮结束，数组中最大值固定

第2轮：

[3 5] 4 1 2 6
3 [4 5] 1 2 6
3 4 [1 5] 2 6
3 4 1 [2 5] 6//第2轮结束，数组中第二大的值固定

第3轮：

[3 4] 1 2 5 6
3 [1 4] 2 5 6
3 1 [2 4] 5 6//第3轮结束，数组中第三大的值固定

第4轮：

[1 3] 2 4 5 6
1 [2 3] 4 5 6//第4轮结束，排序完成

动图加深理解。

参考程序

任何初学编程语言的人，只要会玩数组和循环，冒泡排序都会玩。

不经思考的无脑写法：

void Swap(Datatype* a,Datatype* b){Datatype t=*a;*a=*b;*b=t;
}void bubbleSort(Datatype* a,int n){int i=0,j=0;for(i=0;i<n;i++)for(j=0;j<n-1;j++)if(a[j]>a[j+1])Swap(&a[j],&a[j+1]);
}

尝试优化：每轮冒泡都会选出一个最值放在后面，所以我们可以进行适当剪枝，除去多余的循环。以及冒泡排序可能还没进行完数据就已经有序，所以需要另外做判断。

void bubble(Datatype* a,int n){int i=0,j=0;for(i=1;i<n;i++){//表示这是第i轮排序int judg=0;for(j=1;j<n-i;j++)//表示正在比较的数据if(a[j-1]>a[j]){Swap(&a[j-1],&a[j]);judg=1;}if(judg==0) break;}
}

冒泡排序的特性总结

1. 冒泡排序是一种非常容易理解的排序。也是我目前了解的算法>排序算法里耗时最长的算法>排序算法。若在面试时面试官问冒泡排序，则面试官很大可能对你失去了兴趣，随便问点东西打发面试时间满足公司和其他机构的要求。
   冒泡排序并不是没有意义，它用来教学就有意义。也就是当做其他算法>排序算法的反面教材。

2. 时间复杂度：$O(N^2)$

3. 空间复杂度：$O(1)$

4. 稳定性：稳定

因为冒泡排序进行两两比较的方式，除非修改真值判断方式，否则相同的两个数据不会发生交换。