8.1 排序的基本概念与插入排序

排序的稳定性与分类，直接插入排序、折半插入排序与希尔排序的过程和性能分析。

排序的基本概念

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

在排序过程中，根据数据元素是否完全存放在内存中，可将排序算法分为两类：

• 内部排序：排序期间元素全部存放在内存中的排序；
• 外部排序：排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。

一般情况下，内部排序算法在执行过程中都要进行两种操作：比较和移动。通过比较两个关键字的大小，确定对应元素的前后关系，然后通过移动元素以达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上，基数排序就不基于比较。

直接插入排序

插入排序是一种简单直观的排序算法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。

假设在排序过程中，待排序表 A[0..n−1] 在某次排序过程中的某一时刻状态如下：

要将元素 A[i] 插入已有序的子序列 A[0..i−1]，需要执行以下操作：

1. 查找出 A[i] 在 A[0..i−1] 中的插入位置 k；
2. 将 A[k..i−1] 中的所有元素依次后移一个位置；
3. 将 A[i] 复制到 A[k]。

1void InsertSort(int A[], int n) {
2    int i, j, temp;
3    for (i = 1; i < n; i++)              // 将 A[i] 插入有序区 A[0..i-1]
4        if (A[i] < A[i-1]) {             // 若小于前驱才需要插入
5            temp = A[i];                 // 暂存 A[i]
6            for (j = i - 1; j >= 0 && A[j] > temp; --j)
7                A[j+1] = A[j];           // 大于 temp 的元素后移
8            A[j+1] = temp;               // 插入到正确位置
9        }
10}

性能分析：

• 空间效率：仅使用了常数个辅助单元，空间复杂度为 $O(1)$。
• 时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了 $n - 1$ 趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。
  • 最好情况：表中元素已经有序，此时每插入一个元素，都只需比较一次而不用移动元素，时间复杂度为 $O(n)$；
  • 最坏情况：表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，为 $\sum_{i=2}^{n} i$，总的移动次数也达到最大，为 $\sum_{i=2}^{n}(i+1)$；
  • 平均情况：考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为 $n^2/4$。因此，直接插入排序算法的时间复杂度为 $O(n^2)$。
• 稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序算法。
• 适用性：适用于顺序存储和链式存储的线性表，采用链式存储时无须移动元素。

折半插入排序

从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：① 从前面的有序子表中查找出待插入元素应该被插入的位置；② 给插入位置腾出空间，将待插入元素复制到表中的插入位置。

当排序表为顺序表时，可以对直接插入排序算法做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。

• 折半插入排序仅减少了比较元素的次数，时间复杂度约为 $O(n\log_2 n)$，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数 $n$；
• 而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为 $O(n^2)$；
• 对于数据量不是很大的排序表，折半插入排序往往能表现出很好的性能；
• 折半插入排序是一种稳定的排序算法（相等时继续向右查找）；仅适用于顺序存储的线性表。

希尔排序

从前面的分析可知，直接插入排序算法的时间复杂度为 $O(n^2)$，但若待排序列为”正序”时，其时间效率可提高至 $O(n)$，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

基本思想：先将待排序表分割成若干形如 $L[i, i+d, i+2d, \ldots, i+kd]$ 的”特殊”子表，即把相隔某个”增量” $d$ 的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈”基本有序”时，再对全体记录进行一次直接插入排序。

希尔提出的方法是 $d_1 = n/2$，$d_{i+1} = \lfloor d_i/2 \rfloor$，并且最后一个增量等于 1。在上面的动画中选择”希尔排序”，观察同一子表（紫色）的元素是如何在一趟中被排序的。

即时练习