插入排序-笔记

算法描述

插入排序的过程很像打扑克牌时整理起到手中的牌,我们不断地将右边的牌插入到左边已经理得有序的牌中。我们会看到当前某张牌左侧的所有牌都是有序的,右边的是位置还未确定的,就拿右侧的牌插入到左侧合适的位置,作为分界线的牌可能不断地变化着,直到它移动到最右端为止,此时所有的牌已经有序了。

算法描述:
首先,想象有一个索引指向第二个元素,索引左侧的所有元素已经有序(目前只有一个,就是第一个元素),右侧的元素(包含索引指向的元素)待排序;
接着,将索引指向的元素与左侧有序元素从右向左逐个比较。如果前者小于后者,就交换位置;否则,就表明已经将前者交换移动到正确的位置上了;
如此往复,当索引到达数组最右端时,整个数组就有序了。

算法实现

Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
// 升序排列
public void sort(Comparable[] a) {
int n = a.length;
// i 指向右侧待排序的第一个元素
// 初始时 a[0] 单独已经有序, 所以 i 从 1 开始
for (int i = 1; i < n; i++) {
// 通过交换操作将 a[i] 插入到 a[i-1],a[i-2]...a[0] 中的合适位置
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
}

对插入排序的改进:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 改进: 在内循环中依次将较大元素右移一位, 然后将待排序元素插入到合适的位置。
* 这样就只需要访问数组一次, 而不用交换操作了,这样总的数组访问次数就能减半。
* 注意, 这里的访问仅指对数组的写操作。
*
* @param a
*/
public void sort2(Comparable[] a) {
int n = a.length;
// i 指向右侧待排序的第一个元素
// 初始时 a[0] 单独已经有序, 所以 i 从 1 开始
for (int i = 1; i < n; i++) {
// 保存待插入的数据项
Comparable item = a[i];
// 将待插入的项与有序元素从后向前逐个比较,
// 依次将较大元素向后移动一位。
// j 指向可以被覆盖的位置
int j = i;
for (; j > 0 && less(item, a[j-1]); j--) {
a[j] = a[j - 1];
}
// 插入到合适的位置
a[j] = item;
}
}

算法性能评估

插入排序对于实际应用中常见的某些类型的非随机数组很高效。例如:部分有序的数组、小规模数组、有序数组、主键都相同的数组。对于有序数组和主键都相同的数组,插入排序的运行时间是线性的。而对于这两种数组,选择排序的运行时间都是平方级别的。部分有序的数组、小规模数组是高级排序算法的中间过程,这就是插入排序可以派上用场的地方。

什么是部分有序的数组?如果数组中倒置的数量小于数组大小的某个倍数,就说这个数组是部分有序的。倒置指的是数组中两个顺序颠倒的元素。例如 example 有 11 对倒置:e-a, x-a, x-m, x-p, x-l, x-e, m-l, m-e, p-l, p-e, l-e。几种典型的部分有序的数组:

  1. 数组中的每个元素距离它的最终位置都不远;
  2. 一个有序的大数组接一个小数组;
  3. 数组中只有几个元素的位置不正确。
    事实上,当倒置的数量很少时,插入排序很可能比希尔、归并、快速排序以及堆排序都要快。

对于随机排列的长度为 N 且主键不重复的数组,平均情况下插入排序需要 ~ $N^2/4$ 次比较以及 ~ $N^2/4$ 次交换。最坏情况下需要 ~ $N^2/2$ 次比较以及 ~ $N^2/2$ 次交换,最好情况下需要 N-1 次比较和 0 次交换。

插叙排序需要的交换操作和数组中倒置的数量相同;需要的比较次数大于等于倒置的数量,小于等于倒置的数量加上 (N-1)。每次交换都对应着一次比较,加上 N-1 是因为对于 1 到 N-1 之间的每个 i 都可能需要一次额外的比较,因为遇到第一个不满足交换条件的元素才表明已经插入到正确的位置了。

与其他算法相比较

一个经过验证的经验性结论:插入排序比选择排序快一倍。

参考资源

《算法(第四版)》Robert Sedgewick 等著,第 2 章-排序

0%