3. 插入排序¶
3.1. 插入排序¶
假如你手头有过去两年的电话账单，想把它们按日期整理好，你会 怎么做？ 一个相当自然的办法是：先看前两张账单，把它们排好序。 然后拿起第三张，插到与前两张相对位置正确的地方，依此类推。 每拿起一张账单，就把它放入已经整理好的那叠中。 这个简单的做法就是我们第一个排序算法——插入排序 的灵感来源。
插入排序逐个处理线性表中的记录。
每一轮处理中，把当前记录按正确的位置插入到由已处理记录构成的
已排序线性表中。
下面是一种实现。
输入是存储 \(n\) 条记录的数组 A 。
void inssort(int[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j] < A[j-1]); j--)
swap(A, j, j-1);
}
void inssort(T[] A) {
for (int i=1; i<A.length; i++) // Insert i'th record
for (int j=i; (j>0) && (A[j].compareTo(A[j-1]) < 0); j--)
swap(A, j, j-1);
}
void inssort(Comparable* A[], int n) { // Insertion Sort
for (int i = 1; i < n; i++) // Insert i'th record
for (int j = i; (j > 0) && (*A[j] < *A[j-1]); j--)
swap(A, j, j-1);
}
（注意：为了让这些排序算法的解释尽可能简单，我们的可视化把
数组显示成存储简单整数的样子，而不是更复杂的记录。
但你应当明白，实践中很少会有对简单整数数组排序的需求。
我们几乎总是要排序更复杂的记录，每条记录都带有一个
键 值。
这种情况下，我们必须 有办法
把键值与记录关联起来。
上面代码的 Java 版本使用 int 数组，而 Java (Generic)
版本展示的是使用支持 Comparable 接口的
对象的实现。）
下面我们看到插入排序的前几轮处理。
处理继续进行，每次轮到一条记录。
设当前记录为 \(x\) 。
只要它的值小于紧邻其前的记录，插入排序就会把它向左移动。
一旦遇到小于等于 \(x\) 的键值， inssort 就处理完
了这条记录，因为数组中它左侧的所有记录的键必然更小。
3.2. 插入排序分析¶
虽然最好情况比平均情况和最坏情况快得多，但平均情况和最坏情况 通常是"典型"运行时间更可靠的指标。 不过，有些情形下我们可以预期输入是有序或近乎有序的。 一个例子是：已经排序好的线性表因少量新增元素而轻度乱序； 如果知道乱序程度很轻，用插入排序恢复有序是个好主意。 即使输入不是完全有序的，插入排序的代价也与逆序对的个数成 正比地上升。 所以对"近乎有序"的线性表，插入排序总是很快。 利用插入排序近最好情况运行时间的算法例子有 希尔排序 和 快速排序 。
统计比较次数或交换次数会得到类似的结果。
内层 for 循环每执行一轮就产生一次比较和一次交换，只有
最后一次（即让内层 for 循环测试失败的那次比较）没有
交换。
因此，整个排序过程的交换次数比比较次数少 \(n-1\) 。
最好情况下交换次数为 0，平均情况和最坏情况下为
\(\Theta(n^2)\) 。
后面我们会看到增长率远好于 \(\Theta(n^2)\) 的算法。 因此对于较大的数组，插入排序不如其他算法表现好。 所以在大多数情形下，插入排序不是最佳选择。 但也有一些特殊情形，它恰恰是理想之选。 我们已经知道，输入有序或近乎有序时插入排序表现出色。 另一个适合使用插入排序的时机是数组非常小的时候，因为插入 排序非常简单。 渐近增长率更优的算法往往更复杂，这导致其运行时间中的常数 因子更大。 这意味着对较大的数组它们通常只需要更少的比较，但每次比较的 代价更高。 这个观察似乎用处不大，因为即使是每次比较代价很高的算法，在 小规模输入上也很快。 但有时我们需要对非常小的数组做很多很多次排序。 你现在应该花点时间想一想，什么情况下需要对许多小数组排序。 实际上这种情况经常发生。
关于查找与插入的相对代价如何影响最佳排序算法的选择，参见 Computational Fairy Tales: Why Tailors Use Insertion Sort 。
