排序算法是一类非常经典的算法，说来简单，说难也难。刚学编程时大家都爱用冒泡排序，随后接触到选择排序、插入排序等，历史上还有昙花一现的希尔排序，公司面试时也经常会问到快速排序等等，小小的排序算法，融入了无数程序大牛的心血。
如牛顿所言，正是站在巨人的肩膀上，我们才能望得更远。本文我们就来一起梳理一下排序算法的前世今生。
冒泡排序
冒泡排序是入门级的算法，但也有一些有趣的玩法。通常来说，冒泡排序有三种写法：
- 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
- 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
- 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。
1.1 冒泡排序的第一种写法
代码如下：
public static void bubbleSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j] > arr[j + 1]) {// 如果左边的数大于右边的数，则交换，保证右边的数字最大arr[j + 1] = arr[j + 1] + arr[j];arr[j] = arr[j + 1] - arr[j];arr[j + 1] = arr[j + 1] - arr[j];}}}}
这种写法相当于相邻的数字两两比较，并且规定：“谁大谁站右边”。经过 n-1 轮，数字就从小到大排序完成了。整个过程看起来就像一个个气泡不断上浮，这也是“冒泡排序法”名字的由来。
其中，我们在交换两个数字时使用了一个小魔术：没有引入第三个中间变量就完成了两个数字的交换。这个交换问题曾经出现在大厂面试题中，感兴趣的读者可以细品一下。除了这种先加后减的写法，还有一种先减后加的写法：
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];
这两种交换数字的方式和我们平时常用的写法是等价的（不考虑数字越界的情况）：
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
1.2 冒泡排序的第二种写法
第二种写法是在第一种写法的基础上改良而来的：
public static void bubbleSort(int[] arr) {
// 初始时 swapped 为 true，否则排序过程无法启动
boolean swapped = true;
for (int i = 0; i < arr.length - 1; i++) {
// 如果没有发生过交换，说明剩余部分已经有序，排序完成
if (!swapped) break;
// 设置 swapped 为 false，如果发生交换，则将其置为 true
swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 如果左边的数大于右边的数，则交换，保证右边的数字最大
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 表示发生了交换
swapped = true;
System.out.println("发生了交换。。。");
}
}
}
}
最外层的 for 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是：如果一轮比较中没有发生过交换，则立即停止排序，因为此时剩余数字一定已经有序了。
看下动图演示：
图中可以看出：
- 第一轮排序将数字 6 移动到最右边；
- 第二轮排序将数字 5 移动到最右边，同时中途将 1 和 2 排了序；
- 第三轮排序时，没有发生交换，表明排序已经完成，不再继续比较。
1.3 冒泡排序的第三种写法
第三种写法比较少见，它是在第二种写法的基础上进一步优化：
public static void bubbleSort(int[] arr) {
System.out.println("【原数组】:"+JSON.toJSONString(arr));
boolean swapped = true;
// 最后一个没有经过排序的元素的下标
int indexOfLastUnsortedElement = arr.length - 1;
// 上次发生交换的位置
int swappedIndex = -1;
while (swapped) {
swapped = false;
for (int i = 0; i < indexOfLastUnsortedElement; i++) {
if (arr[i] > arr[i + 1]) {
System.out.println("【进行了交换】 左数:"+arr[i]+" 右数:"+arr[i+1]);
// 如果左边的数大于右边的数，则交换，保证右边的数字最大
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
// 表示发生了交换
swapped = true;
// 更新交换的位置
swappedIndex = i;
System.out.println("【排序后数组】 : "+JSON.toJSONString(arr));
} else {
//System.out.println("【未进入判断】 左数:"+arr[i]+" 右数:"+arr[i+1]);
}
}
// 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
indexOfLastUnsortedElement = swappedIndex;
}
}
经过再一次的优化，代码看起来就稍微有点复杂了。
最外层的 while 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。
在下一轮比较时，只需比较到上一轮比较中，最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换，必然已经有序了。
当一轮比较中从头到尾都没有发生过交换，则表示整个列表已经有序，排序完成。
测试：
public void test() {
int[] arr = new int[]{6, 2, 1, 3, 5, 4};
bubbleSort(arr);
// 输出: [1, 2, 3, 4, 5, 6]
System.out.println(Arrays.toString(arr));
}
<br />冒泡排序从 1956 年就有人开始研究，之后经历过多次优化。它的空间复杂度为 O(1)，时间复杂度为 O(n^2)，第二种、第三种冒泡排序由于经过优化，最好的情况下只需要 O(n) 的时间复杂度。<br />最好情况：在数组已经有序的情况下，只需遍历一次，由于没有发生交换，排序结束。<br /><br />最差情况：数组顺序为逆序，每次比较都会发生交换。<br /><br />但优化后的冒泡排序平均时间复杂度仍然是 O(n^2)，所以这些优化对算法的性能并没有质的提升。正如 Donald E. Knuth（1974 年图灵奖获得者）所言：“冒泡排序法除了它迷人的名字和导致了某些有趣的理论问题这一事实外，似乎没有什么值得推荐的。”<br />不管怎么说，冒泡排序法是所有排序算法的老祖宗，如同程序界经典的 “Hello, world” 一般经久不衰，总是出现在各类算法书刊的首个章节。
但面试时如果你说你只会冒泡排序可就太掉价了，下次我们就来认识一下他的继承者们。(下次一定…)
若有收获，就点个赞吧
0 人点赞
