插入排序(Insertion Sort)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

插入排序(Insertion Sort)

2017-03-11

概念

插入排序是一种简单直观的排序算法.
通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

举例

例1

现有一组数组[5, 6, 3, 1, 8, 7, 2, 4],共有八个记录,排序过程如下:

  1. [5] 6 3 1 8 7 2 4
    我们把已排好序的数列用[]括起来,我们直接把第一个元素放入已排序数列
  2. [5 6] 3 1 8 7 2 4
    然后我们把第二个元素从已排序数列的最后一个元素开始比较,如果比左边的元素小,就向左交换位置,直到找到自己的位置,也就是把第二个元素插入到已排序数列正确的位置上.
  3. [3 5 6] 1 8 7 2 4
    对第三个元素重复步骤二,通过比较找到在已排序数列中的位置
  4. [1 3 5 6] 8 7 2 4

  5. [1 3 5 6 8] 7 2 4

  6. [1 3 5 6 7 8] 2 4

  7. [1 2 3 5 6 7 8] 4

  8. [1 2 3 4 5 6 7 8]
    直到所有数都被插入到已排序数列,排序完成.

例2

假定有一个数组[5, 7, 4, 10, 9],我们要把这个数组按从小到大排列

  1. 把数列看作两部分,前面部分是排序好的,后面部分是还没有排序的.
  2. 我们先把第一个数看作是已经排序好的数列,因为只有一个数,所以它当然是有序的(对于有序数列来说),即看成[5]和[7, 4, 10, 9]两部分
  3. 然后从第二个数开始,也就是从未排序数列的第一个数开始,将它从已排序数列的后(右)边开始(当然你也可以从前(左)边开始),分别与已排序数列的每一个数进行比较.
  4. 如果发现比自己大的数,就与这个数交换位置,如果发现比自己小的数,就停止比较,开始下一轮操作,当然,如果已经交换到和数列的第一个数交换的时候,也开始下一轮操作.
  5. 这个例子中,7和5比较,7比5大,所以不用交换,数列变成[5, 7]和[4, 10, 9].
  6. 重复这个步骤,知道所有未排序的数都被插入正确的位置.

插入排序的插入,意思就是我们维护一个新的数列,每次都把数插入到它正确的位置上.

代码实现

按照定义的实现如下,把数组分为两部分,前面i位是已排序的,后面的都是待排序的.

protected int[] Sort(int[] num) {
    for (int i = 1; i < num.length; i++) {
        int j = i - 1;
        while (j >= 0) {
            if (num[j] < num[i])
                break;
            j--;
        }
        if (j != i - 1) {
            int temp = num[i];
            int k = i - 1;
            while (k > j) {
                num[k + 1] = num[k];
                k--;
            }
            num[k + 1] = temp;
        }
    }
    return num;
}

复杂度及稳定性

时间复杂度 $O(n^2)$

如果目标是把$n$个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。

  • 最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需$(n-1)$次即可。
  • 最坏情况就是,序列是降序排列,那么此时需要进行的比较共有${1\over2}n(n-1)$次。

插入排序的赋值操作是比较操作的次数加上$(n-1)$次。平均来说插入排序算法复杂度为$O(n^2)$。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)

空间复杂度 $O(1)$

因为插入排序也是一种原地排序算法,所以只需要一个辅助空间用于交换

稳定性

在排序中遇到相同的元素,并不会交换它们的位置,所以插入排序是稳定的.

优化

这两种说是优化方案,不如说是插入排序的两种不同写法,因为这两种写法并没有显著提升算法速度

方案1

在每次比较操作发现新元素小于等于已排序的元素时,我们的做法是把有序数列中大于新元素的数统一向后移动一位,来腾出位置,这样做交换操作代价比较大.我们现在要做的是将新元素取出,从左到右依次与已排序的元素比较,如果已排序的元素大于新元素,那么将该元素移动到下一个位置,接着再与前面的已排序的元素比较,直到找到已排序的元素小于等于新元素的位置,这时再将新元素插入进去

protected int[] Sort(int[] num) {
    for (int i = 1; i < num.length; i++) {
        int temp = num[i];
        int j = i;
        while (j > 0 && num[j - 1] > temp) {
            num[j] = num[j - 1];
            j--;
        }
        num[j] = temp;
    }
    return num;
}

方案2

这个方案直接让新元素一个个向前比较,如果遇到大的就交换,遇到小的就停止

protected int[] Sort(int[] num) {
    for (int i = 1; i < num.length; i++) {
        for (int j = i - 1; j >= 0 && num[j] > num[j + 1]; j--) {
            int temp = num[j];
            num[j] = num[j + 1];
            num[j + 1] = temp;
        }
    }
    return num;
}

评论