11-排序（上）：为什么插入排序比冒泡受欢迎？

Posted on | Post modified:
Words count in article: 2k | Reading time ≈ 7

在接下来的三讲里，将会讲解最常用的几种排序方法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度把它们分成了三类，分三讲来讲解。

sortAll1

思考题：插入排序和冒泡排序的时间复杂度相同，都是O(n^2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？

如何分析一个算法？

学习排序算法，我们处理学习他的算法原理、代码之外，更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法，要从哪几个方面入手呢？

排序算法的执行效率

对于排序算法执行效率的分析，我们会从这几个方面来衡量：

  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数、低阶
  3. 比较次数和交换（移动）次数
排序算法的内存消耗

前面讲过，算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过、针对排序算法的空间复杂度，我们引入一个新的概念 原地排序（Sorted in place）。原地排序排序算法，就是特指空间复杂度为O(1)的排序算法。接下来的三种算法都是原地排序算法。

排序算法的稳定性

仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

稳定性有什么作用呢？下面我们来看一个例子：

比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？

借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，我们用稳定排序算法，按照订单金额重新排序。

orderSort

稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。

下面我们来看看这三种算法之间的比较：

冒泡排序（Bubble Sort）

它只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行 比较，看是否满足大小关系要求。

如图：
bubbleSort

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//冒泡，在此添加一个标志位，减少交换次数。
void bubbleSort(int[] a, int n) {
  if(n <= 1) {
    return ;
  }
  for(int i = 0;i < n; ++i) {
    boolean flag = false;  // 创建一个标志位，如果为true表示有数据交换，反之没有。
    for(int j = 0;j < n - i - 1; ++j) {
      if(a[j] > a[j+1]) {
        int temp = a[j];
        a[j] = a[j+1];
        a[j+1] = temp;
        flag = true;
      }
    }
    if(!flag) {  // 如果没有数据交换就跳出
      break;
    }
  }
}

算法分析：
稳定性：当元素相等时不交换位置，所以是稳定的。
空间复杂度：原地排序算法，为O(1)。
时间复杂度：

  1. 最好的情况也叫做满有序度：O(n)。
  2. 最坏的情况也叫做满逆序度：O(n^2)。
  3. 平均情况：O(n^2)。

插入排序（Insertion Sort）

插入排序将数组分为两个区，已排序区、未排序区。每次都在未排序区中取出一个数插入到已排序区中的合适位置，直至未排序区为空。

如图：
insertionSort

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 插入排序
void insertionSort(int[] a, int n) {
  if(n <= 1) {
    return ;
  }
  for(int i = 0; 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)。
时间复杂度：

  1. 最好情况：O(n)。
  2. 最坏情况：O(n^2)。
  3. 平均情况：O(n^2)。

选择排序（Selection Sort）

选择排序类似于插入排序，也分为已排序和未排序两个区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

如图：
selectionSort

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 选择排序
void selectionSort(int[] a, int n) {
  if(n <= 1) {
    return ;
  }
  for(int i = 0; i < n; ++i) {
    int min = a[i];
    int flag = i;   // 最小元素的下标
    int j = i + 1
    for(; j < n; ++j) {    // 寻找最小元素的下标
      if(a[j] < min) {
        flag = j;
      }
    }
    if(flag != i) {
      int temp = a[i];
      a[i] = a[flag];
      a[flag] = temp;
    }
  }
}

算法分析：
稳定性：由于该排序每次都要寻找未排序元素中的最小值，并和前面的元素交换位置，这样就破坏了稳定性。
空间复杂度：原地排序。
时间复杂度：

  1. 最好情况：O(n^2)。
  2. 最坏情况：O(n^2)。
  3. 平均情况：O(n^2)。

解答开篇

为什么冒泡排序和插入排序的时间复杂度都是O(n^2),都是原地排序算法，而后者却更受欢迎呢？我们通过观察它们的代码实现就可以知道：冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡需要三个赋值操作，而插入只需要一个。虽然冒泡排序和插入排序在时间复杂度上是一样的，都是O(n^2)，但是如果我们希望把性能优化到极致，那肯定首选插入排序。

插入排序的算法思想也有很大的优化空间，比如希尔排序。

总结

想要分析、评价一个排序算法，需要从执行效率，内存消耗和稳定性三个方面来看。学习排序算法中点掌握它们的分析方法。下面是三种算法的比较：
B-I-S-Summary

课后思考

特定算法是依赖特定的数据结构的。这一讲讲的几种排序算法都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作嘛？如果能，那相应的时间、空间复杂度又是多少呢？

@双木公子
对于老师所提课后题，觉得应该有个前提，是否允许修改链表的节点value值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。

有问题？发送 issues 给我~

0%