7.3 插入排序

插入排序是每次将一个记录 RiR_i 插入到一个已排序好的序列 R0,R1,,Ri1(K0K1Ki1)R_0, R_1, \cdots, R_{i-1} (K_0 \leq K_1 \leq \cdots \leq K_{i-1}) 中,并使得插入后形成的长度为 ii 的序列也是有序的。初始时,有序序列为 R0R_0,然后依次插入 R1,R2,,Rn1R_1, R_2, \cdots, R_{n-1}。这种排序策略由函数 insertion_sort 实现。

void insertion_sort(element list[], int n)
{
    int i, j;
    element next;
    for (i = 1; i < n; i++) {
        next = list[i];
        for (j = i-1; j >= 0 && next.key < list[j].key; j--)
            list[j+1] = list[j];
        list[j+1] = next;
    }
}

在最坏情况下,插入之前的内层循环需进行 ii 次比较操作。因此,将一个记录插入到有序序列的计算时间为 O(i)O(i)。由于外层循环的循环变量 i=1,2,,n1i = 1, 2, \cdots, n-1 都被执行,故在最坏情况下,总的计算时间是:O(i=0n1i)=O(n2)O(\sum^{n-1}_{i=0}i) = O(n^2)

还可以通过检查输入表的相对无序性来估计插入排序的计算时间。为了计算相对无序性,需测量每个记录是 「左无序」 的区域长度。

  • 「左无序 LOO, left out of order」 的定义是:RiR_i 是 LOO 的,当且仅当 Ri<max0j<i{Rj}R_i < \max_{0\leq j < i}\{R_j\}

插入只对 LOO 记录执行迭代。如果左无序记录有 kk 个,则插入排序的计算时间为 O((k+1)n)O((k+1)n),在最坏情况下插入排序的计算时间仍然是 O(n2)O(n^2)。可以证明其平均时间也是 O(n2)O(n^2)

所以,当只有少数记录是 LOO 记录时,即 knk \ll n 时,插入排序的运行效果是非常好的。此外,可以很容易验证插入排序是稳定的。正因为有这些优点和插入排序方法的简单性,使插入排序非常适合规模小的 (n20)(n \leq 20) 序列表。

算法若干变形

  1. 折半插入排序: 利用折半查找来替换函数 insertion_sort 中的顺序查找,这样可以减少插入排序中的比较次数。此时记录的移动次数仍然保持不变。
  2. 链表插入排序: 用动态链表代替数组表示表中的元素。这样,在插入时就只需调整链域,而不需移动记录。

results matching ""

    No results matching ""