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的位置自然就确定了(它已经没得选了)。

转载自 Harttle.Land

本文采用 知识共享署名 4.0 国际许可协议(CC-BY 4.0)进行许可。转载请注明来源: https://snowfrs.com/2015/09/28/insertion-bubble-sort.html 欢迎对文中引用进行考证,欢迎指出任何不准确和模糊之处。