冒泡插入和选择排序的比较

冒泡排序与插入排序

冒泡排序和插入排序算法的时间复杂度是O(n²)，但是在实际应用中更多的是使用插入排序，原因是什么呢？

算法的执行效率

可以从一下几个方面考虑二者的差别：

• 最好情况、最坏情况、平均情况的时间复杂度

  要区分这三种时间复杂度是因为我们可以知道排序算法在不同数据下的性能表现。

• 时间复杂度的系数、常数、低阶

  时间复杂度反应的数据规模n很大的时候的一个增长趋势，所以它会经常忽略系数、常数、低阶。但是实际开发中排序的数据规模可能是10、100或者1000个这种小规模数据，这时系数或者常数可能起到决定性作用，这时就需要上述三种因素考虑进来。

• 比较次数和交换（或移动）次数

  基于比较的排序算法总是会设计两种操作：比较和移动。所以也要考虑这两种操作带来的影响。

排序算法的内存消耗

算法内存消耗可以通过空间复杂度也衡量，就是算法执行过程中需要用到的内存空间与数据量之间的关系。有一种叫原地排序的概念是指空间复杂度为O(1)的排序算法。

排序算法的稳定性

如果待排序的序列中存在值相等的元素，经过排序后相等元素之间原有的先后顺序不变，我们就称这个算法是稳定排序算法，否则就称之为不稳定排序算法。

冒泡排序

冒泡排序便利整个数据集，通过比较相邻元素的大小关系，进行互换操作。一次冒泡会至少一个元素移动到它应该在的位置，重复n次就完成了n个数据的排序工作。比如这个例子：

可以看出经过6次比较，我们找到了最大数6，然后重复上面的步骤:

最后就得到了有序的数据集。

其实这里面有可以优化的地方，如果某次冒泡操作没有执行数据交换时，就说明序列已经是有序的了，就可以结束冒泡操作了。比如下面这个例子：

实际上只需要四次冒泡操作就完成了排序操作了。

冒泡排序算法代码如下：

// 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

• 冒泡排序是原地排序算法吗？

是的，因为排序过程中只涉及到相邻元素的交换，没有另外占据内存空间，空间复杂度是O(1)，所以是原地排序算法。

• 冒泡排序算法是稳定排序算法吗？

是的。因为在冒泡过程中遇到两个相等的元素时我们是不尽兴数据交换的，相同大小的数据在排序前后的顺序不会改变，所以是稳定排序算法。

• 冒泡排序算法的时间复杂度是多少？

最好情况下，数据集已经是有序的了，只需要进行一次冒泡就可以确定排序完成了，所以时间复杂度是O(n)；
最坏情况下，数据正好是反序的，需要进行n次冒泡才能确定排序完成，所以时间复杂度是O(n²)。

平均时间复杂度呢？平均时间复杂度牵扯到概率论的一些知识，假设有一个n个数据的数组，这个数组有n!中排列方式，这里加入两个概念：有序度和逆序度两个概念。

有序度是数组中具有有序关系的元素的个数，他们的关系就是这样的：

a[i] < a[j] && i < j

图示一下，你会更直观了解这个有序度是多少：

对于一个倒序排列的数组，它的有序度就是0.对于一个完全有序的数组，它的有序度就是1+2+3+……+(n-1)=n*(n-1)/2，我们称这种完全有序的数组的有序度为满有序度。

逆序度与有序度正好相反，也就是：

a[i] > a[j] && i < j

这里有一个公式：逆序度 = 满有序度 - 有序度。排序其实就是增加有序度，减小逆序度的过程，最终要达到满有序度的结果。

假如一个数组初始状态是4，5,6，3,2,1，其中有序元素对有(4,5),(4,6),(5,6)，所以有序度是3，而满有序度可以通过公式n*(n-1)/2计算出来是15。冒泡排序包含比较和交换两种操作，每交换一次有序度就加1，不管算法怎样，交换次数是确定的，就是逆序度，也就是15 - 3 = 12次，要进行12次交换才能达到最终要求。

对于n个数据的数组，平均要交换多少次呢？最坏情况下有序度是0，要交换n(n-1)/2次，最好情况下有序地是n(n-1)/2，要交换0次，我们可以去中间值n(n-1)/4来表示有序度既不是最高也不是最低的平均情况。也就是说平均情况下要交换n(n-1)/4次，最终时间复杂度忽略掉系数、常数、低阶就是O(n²)。这个推到过程不严格，但是具有一定的参考性。

插入排序

插入排序就是遍历一个有序数组，根据指定数据的大小寻找合适的位置向数组中插入这个数据，如下图所示：

插入排序是动态的排序过程，且排序过程中序列一直保持有序。

插入排序的具体实现思路就是把数组中的元素分成两个区间：已排序取间和未排序取间，初始状态时已排序区间就是首元素，从第二个元素开始到最后一个元素都是未排序取间。然后从未排序区间中顺序取出所有元素在已排序区间的合适位置插入，这个过程中已排序区间的数据是一只有序的。重复这个过程直到未排序区间为空。

插入排序中也包含两种操作，但是与冒泡不同的是它没有交换，而是元素移动，除了元素的移动，还有一个元素的比较，这个与冒泡一样（废话，不比较怎么排序！囧）。当需要插入一个元素是，我们拿这个元素与已排序区间的所有元素比较大小，找到合适的位置插入。找到合适的插入点后需要将插入点后的元素都往后移动一位，腾出位置给要插入的元素。

就寻找合适插入位置这个问题，有不同的方法，可以从头到尾搜索已排序区间，也可以从尾到头，比较次数是有区别的。不过有一个特点就是移动操作的次数是固定的，等于逆序度（其实想想排序就是消除逆序度的过程，有多少个逆序度就需要移动多少次元素，因为要消除一个逆序度就需要进行一次数据交换，一次数据交换就是一次移动操作，有点绕，看一下图片理解一下把）。

插入排序实现代码：

// 插入排序，a 表示数组，n 表示数组大小
public void insertionSort(int[] a, int n) {
  if (n <= 1) return;

  for (int i = 1; i < n; ++i) {
    int value = a[i];
    int j = i - 1;
    // 查找插入的位置
    for (; j >= 0; --j) {
      if (a[j] > value) {
        a[j+1] = a[j];  // 数据移动
      } else {
        break;
      }
    }
    a[j+1] = value; // 插入数据
  }
}

三个问题：

• 插入排序是原地排序算法吗？

是的。因为插入排序算法运行过程中不需要额外的内存空间，空间复杂度是O(1)，所以是原地排序算法。

• 插入排序是稳定的排序算法吗？

是的。因为对于值相等的元素我们不进行数据的移动操作，只需要将后出现的元素插入到先出现的元素之后的位置就行了，原有的顺序保持不变，所以快速排序是稳定的排序算法。

• 插入排序的时间复杂度是多少？

最好的情况，要排序的数组已经是有序的，不需要移动任何数据，只需要尾到头在已排序区间内查找插入的位置，每次只需要比较一个数据就能确定插入的位置，最后比较下来一共需要比较n-1次就可以了时间复杂度就是O(n-1)，省略到常数后就是O(n)。需要注意的是这里采用的是从尾到头遍历已排序的区间，如果从头到尾遍历时间复杂度是不一样的，是O(n*(n-1)/2)(具体你们自己分析把)。

最坏的情况，数组是逆序的，每次插入都需要将数据插入到数组的第一个位置，也就是每次都需要移动所有已排序区间内的元素，这种情况下到排序完成需要移动的元素的次数就是1+2+3+……+n-1=n*(n-1)/2，最后的时间复杂度就是O(n²)。

往数组中插入一个数据的平均复杂度是O(n)，对于插入排序来说，每次操作都相当于在数组中插入一个数据，循环n次执行插入操作，所以插入排序的平均时间复杂度就是O(n²)。

选择排序

选择排序与插入排序思路类似，选择排序也分已排序区间和未排序区间，选择排序的过程就是从未排序区间中找出最小的元素放到已排序区间的末尾（想想这个插入排序的区别，其实就是特殊的插入排序，我们总是选择未排序区间中最小的元素，插入的位置也固定为已排序区间的末尾，插入排序不指定要插入的数据，而是从未排序区间顺序选取要插入的数据，也不指定插入的具体位置，一切根据数据大小规则进行插入位置的选择）。

排序过程就是上图所演示的那样，还是那三个问题：

• 选择排序是愿你排序算法吗？

是的，因为选择排序执行过程中没有申请额外的内存空间，空间复杂度是O(1)，所以是原地排序算法。

• 选择排序的时间复杂度是多少？

最好情况下，数组是有序的，取出最小元素需要比较n-1 + n-2 + …… + 2 + 1 = n*(n-1)/2， 时间复杂度是O(n²)。

同样，最坏情况下，数组是逆序的，取出最小元素也需要比较n-1 + n-2 + …… + 2 + 1 = n*(n-1)/2次，时间复杂度也是O(n²)。

最好和最坏情况时间复杂度都是O(n²)，所以平均时间复杂度也是O(n²)。

• 选择排序是稳定排序算法吗？

不是的，比如一个数组内有这几个元素{4, 5, 4, 2, 6}，排序时首先选择一个最小的元素2，与第一个位置的4交换位置，那么最终两个4的位置就交换了，这就不稳定了，所以选择排序不是稳定排序算法，就是因为它引入了跨区间的元素交换。（冒泡排序也有元素交换，但是冒泡是稳定的，这是因为冒泡交换的始终是两个相邻的元素）

由于选择排序是不稳定的，所以相对来说应用场景就受限很多。

实际使用中插入排序为什么比冒泡受欢迎？

从时间复杂度来看，二者都是O(n²)，不管怎么优化，元素的移动次数都等于原始数据的逆序度。但是从二者代码的实现上，插入排序只需要一个赋值操作，而冒泡需要3个，（这是因为插入进行的是数据移动，而冒泡是数据交换，数据搬移很简单，直接赋值就行，但是数据交换需要中间变量，所以就需要3个赋值语句）具体代码比较如下：

冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true;
}

插入排序中数据的移动操作：
if (a[j] > value) {
  a[j+1] = a[j];  // 数据移动
} else {
  break;
}

如果把一个赋值语句的时间粗略统计为一个单位时间，分别用冒泡排序和插入排序对一个K个元素的数组进行排序，用冒泡法时，需要K次数据交换，每次需要3个赋值语句，总耗时就是3K个单位时间，而插入排序只需要K个单位时间。

插入排序的优化是希尔排序，可以试着了解一下。

总结

排序算法的评价标准需要从执行效率、内存消耗和稳定性三个方面进行考虑，冒泡、插入、选择排序的总结如下图所示：

其实这三种排序算法实际中单独应用的并不多，但是可以作为开拓思维的基础算法，不过这些算法会作为某些排序函数的一部分得到应用。

问题

如果将上述算法以来的数据结构由数组变为链表，三种算法还能正常工作吗？能得话他们呢得时间复杂度、空间复杂度又是多少？（这里只进行节点间得移动，不能该节点的值）

冒泡排序：节点的比较次数还是一样的，但是节点的交换相较于数组更加复杂，时间复杂度和空间复杂度不变，但是由于交换操作更加复杂，时间复杂度的系数会变大。

插入排序：比较次数没有变化，插入操作会简单一点，不需要移动所有元素，只需要直接插入即可，时间复杂度和空间复杂度也没有变化，但是时间复杂度系数会减小。

选择排序：比较和交换次数没有变化，所以时间和空间复杂度都没有变化吗，但是交换操作会比数组复杂，所以时间复杂度系数会变大。

---

参考文章来源：极客时间

链接地址：为什么插入排序比冒泡排序更受欢迎？

2018.11.13 北京 晚上大雾