你的同龄人写不出冒泡排序

vlambda
2021-05-19

你的同龄人写不出冒泡排序

大家好，我是小吴。

这个案例《编程珠玑》一书中的一个结论很相似：给予他们充足时间的情况下，有百分之九十以上的人无法编写出完全准确的二分查找法的代码。

估计不少读者看到这两个例子会觉得难以置信，这不是最基础的东西么？

但事实的确如此，上述的案例二我曾经在知乎分享过，很多人尝试了一下没写对，不信的话你可以花两分钟在留言区默写一下二分查找法的代码，然后和下面给出的一个参考答案进行对比：

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // 防止溢出
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
 }

今天的主题不是二分查找法，而是冒泡排序，所以不深入聊二分法，我想手把手带你写对冒泡排序与理解它的优化过程，毕竟，学会了就超过了一半的同龄人呀。

在这里先问大家一个问题：应该大部分人都知道冒泡排序有两个 for 循环，你是先写内循环还是外循环？

这个问题先按下不表，继续往下看。

首先，我们来理解冒泡排序的原理：

1、每一次遍历数组，都去不断地比较相邻的两个元素，如果它们的顺序不对，就交换这两个元素，比如把较大的换到后面。第一次遍历可以把最大的元素确定下来，放在最后的位置。

2、第二次遍历可以确定第二大的元素，依次类推。

3、这样遍历 N 次后，整个数组就变成递增有序。

这个原理很好理解也很好记忆，所以我们按照这个原理的步骤来思考如何写代码。

一开始需要遍历数组，从头遍历到尾，代码如下:

// begin 从 0 开始和从 1 开始都是可以的，但个人习惯选择 1 开始
for (int begin = 1; begin <= array.length - 1; begin++) {

}

比较相邻的两个元素，如果它们的顺序不对，就交换这两个元素（默认增序）。

if (array[ begin ] < array[ begin - 1 ]) {
 int tmp = array[ begin ];
 array[ begin ] = array[ begin - 1 ];
 array[ begin - 1 ] =  tmp;
}

联合起来就是：

//为了方便后续的表述，我们把这段代码称为初始代码
for (int begin = 1; begin <= array.length - 1; begin++) {
  if (array[begin] < array[begin - 1]) {
     int tmp = array[begin];
     array[begin] = array[begin - 1];
     array[begin - 1] =  tmp;
 }
}

为了方便后续的表述，我们把上面这段代码称为初始代码。

写到这，我们就已经把数组中最大的元素挑选出来了，同时代码也完成了 50%。

我们接下来去完成剩下的 50% 的代码，这部分代码的思考点在于如何做到在第二次遍历去确定第二大的元素。

begin 从 1 开始到 array.length - 1 结束挑选出了最大的元素放到了数组的末尾，所以在接下来的遍历中，数组末尾的元素不需要去考虑，即 begin 从 1 开始到 array.length - 2 结束挑选出第二大的元素。

所以，第二次遍历的代码和第一次遍历的代码应该是一样的，唯一的区别点在于 begin 的结束值。

基于这个思考，改造初始代码。

begin 的开始都是在 1 开始的，但结束的位置不是确定的位置 array.length - 1，而是一个变量，我们把它称为 end。

for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
     int tmp = array[begin];
     array[begin] = array[begin - 1];
     array[begin - 1] =  tmp;
 }
}

end 范围是什么呢？

一开始是 array.length - 1，挑选出最大的元素后缩小为 array.length - 2 去挑选第二大的元素，然后再缩小为 array.length - 3 去挑选到第三大的元素，不断的递减，直到没得挑了。

什么时候没得挑？

直到下标为 1 （图中下标为 1 的元素值刚好也为 1 ）的那个位置就没得挑了。

所以，end 的最小值可以为 1。

分析到这，冒泡排序的代码就完成了。

//为了表述方便，我们把这块代码称为第一版代码
for (int end = array.length - 1; end >= 1; end--) {
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
  }
 }
}

然后回到我们之前按下不表的那个问题：冒泡排序有两个 for 循环，要先写内循环还是外循环。

答案就是，按照我们最容易理解的思路，需要先去写内循环，再去写外循环。

在笔试的时候，当你顺利地写对冒泡排序的代码时，正常的流程就是面试官开始和你讨论冒泡排序的优化。

一个问题需要优化，代表它的一些特殊情况没有得到很好的处理。

那么，第一版冒泡排序代码存在哪些情况没有处理好呢？

第一版冒泡排序代码的每一步操作都是在把相对最大的元素挪到最后的位置，如果一开始数组中的元素就是按照从小到大的顺序进行排列，那么第一版代码中的比较操作就是在做无用功。

所以，我们把优化的方向定在如何处理这种完全有序的情况，完全有序的情况有可能发生在一开始数组就是有序的，也有可能操作到一部分后就完全有序了，无论是哪种情况，当发现数组已经完全有序，我们就停止就行了。

怎么判断当时的情况是否完全有序呢？

先默认此时的数组是有序的，如果发生了交换操作，那么就不是有序的，继续运行代码，否则停止。

第一版的优化代码就来了：

//为了表述方便，我们把这块代码称为第一版的优化代码
for (int end = array.length - 1; end >= 1; end--) {
    boolean sorted = true;
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
            sorted = false;
  }
 }
    if (sorted) break;
}

接下来，再来看第二种特殊情况，排序过程中发现前面大部分是无序而尾部有序，那么 end 就不用从 array.length - 1 递减到 array.length - 2 再递减到 array.length - 3 ，而是可以骤降，直接减到array.length - 3 的位置。

对于这种情况，思考的方向在于如何定位到局部有序的初始位置。

在每一轮的遍历中如果发生了交换操作，那么最后一次交换的位置是在变化的，当交换的位置不再发生改变时，意味着当前的这次遍历中最后的部分元素是有序的了。

我们需要去记录最后一次交换的位置，然后把记录到的位置赋值给 end，这样 end 可以直接略过那部分有序数组的操作。

代码如下：

for (int end = array.length - 1; end >= 1; end--) {
    int lastExchange = 1;
 for (int begin = 1; begin <= end; begin++) {
  if (array[begin] < array[begin - 1]) {
   int tmp = array[begin];
   array[begin] = array[begin - 1];
   array[begin - 1] =  tmp;
      lastExchange = begin;
  }
 }
    end = lastExchange;
}