Wikipedia: 插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2)，最好情况下都是 O(n)，空间复杂度是 O(1)。 这两者思路非常简单就不给伪码了，下文为C++的实现。

插入排序

void insertion_sort(vector<int> v){
    for(int i = 1; i < v.size(); ++i){
        int tmp = v[i], j = i - 1;
        for(; j >= 0 && v[j] > tmp; --j){
            v[j+1] = v[j];
        }
        v[j+1] = tmp;
    }
}

注意v[j] > tmp没有写作v[j] >= tmp，因此提供了排序的稳定性。插入排序可以是稳定的排序算法。

实现思路是这样的：

  1. 认为第一个元素是排好序的，从第二个开始遍历。
  2. 拿出当前元素的值，从排好序的序列中从后往前找。
  3. 如果序列中的元素比当前元素大，就把它后移。直到找到一个小的。
  4. 把当前元素放在这个小的后面（后面的比当前大，它已经被后移了）。

插入排序的复杂度

最好和最好时间复杂度：

  • 如果序列本来是排好序的，那么会触发最好情况。这时只需要n-1次比较即可，没有任何元素移动。所以最好情况下时间复杂度是 O(n)。
  • 如果序列是逆序排列的，那么会触发最坏情况。这时每个元素都需要一步一步地挪到序列首部。所以最坏情况下的时间复杂度是 O(n^2)。

平均情况下的时间复杂度是 O(n^2)，对于几百个元素仍然是很快速的算法，因为实现简单。所以STL中的qsort都会以插入排序作为快速排序的补充来处理少量元素。 空间复杂度当然是 O(1) 的，插入排序是采用迭代策略实现的，只用了常数个变量而已。

冒泡排序

冒泡排序想必是平生见过最简单的排序算法：

void bubble_sort(vector<int> v){
    for(int i=0; i<v.size()-1; i++){
        for(int j=0; j<v.size()-1-i; j++){
            if(v[j] > v[j+1]) swap(v[j], v[j+1]);
        }
    }
}

这里v[j] > v[j+1]没有用>=，同样是为了提供稳定的排序。

  1. 从第一个元素开始，比较相邻的一对元素。
  2. 如果前面的比后面的大，交换它们。
  3. 一轮遍历之后最大的元素一定会位于序列结尾。
  4. 重复1-3，每次将剩下的元素中最大的放到剩下元素组成序列的结尾。

冒泡排序的复杂度

可以看到上述的冒泡排序实现中，任何输入的算法复杂度都是 O(n^2)，空间复杂度是常数 O(1)。但可以记录一个不需要交换的位置，把最好情况的时间复杂度降到 O(n)：

void bubble_sort(vector<int> v){
    int end = v.size();
    while(end > 1){
        int new_end = 0;
        for(int j=0; j<end-1; j++){
            if(v[j] > v[j+1]){
                swap(v[j], v[j+1]);
                new_end = j+1;
            } 
        }
        end = new_end;
    }
}

上述代码中维护了一个已排好序的序列：$[end, N)$（N是数组大小），每次冒泡会记录最大的那个泡泡的位置作为end。 直到end == 1时，说明整个序列已经排好。

因为冒泡排序中每次冒泡都相当于选最大值放到序列结尾，所以$[end, N)$不仅是有序的，而且位置是正确的。 所以end == 1时，$[1, N)$已经获得了正确的位置，那么元素0的位置自然就确定了（它已经没得选了）。

本文采用 知识共享署名 4.0 国际许可协议（CC-BY 4.0）进行许可，转载注明来源即可： https://harttle.land/2015/09/28/insertion-bubble-sort.html。如有疏漏、谬误、侵权请通过评论或 邮件 指出。