数据结构之插入排序

直接插入排序

基本思想：

插入排序是一种简单、直观的排序方法。其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，直到所有记录插入完毕。

直接插入排序步骤：

假设当前有序序列为 $ L[1..i-1] $，无序序列为 $ L[i..n] $。要将元素 $ L[i] $ 插入到有序的子序列 $ L[1..i-1] $ 中，执行以下操作：

查找 $ L[i] $ 在 $ L[1..i-1] $ 中的插入位置 $ k $。
将 $ L[k..i-1] $ 的所有元素向后移动一个位置。
将 $ L[i] $ 复制到 $ L[k] $。

上述过程重复 $ n-1 $ 次，直到所有元素排序完毕。排序可以采用 就地排序（即原地排序），空间复杂度为 $ O(1) $。

直接插入排序代码示例：

void InsertSort(ElementType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        if (A[i] < A[i-1]) {
            A[0] = A[i];  // 哨兵
            for (j = i-1; A[0] < A[j]; --j) {
                A[j+1] = A[j];  // 元素后移
            }
            A[j+1] = A[0];  // 插入到正确位置
        }
    }
}

示例：

假定初始序列为 $ [49, 38, 65, 97, 76, 13, 27, 49] $，使用直接插入排序的过程如下：

步骤	排序状态
初始	49, 38, 65, 97, 76, 13, 27, 49
$ i = 2 $	(38), 49, 65, 97, 76, 13, 27, 49
$ i = 3 $	(38, 49), 65, 97, 76, 13, 27, 49
$ i = 4 $	(38, 49, 65), 97, 76, 13, 27, 49
$ i = 5 $	(38, 49, 65, 76), 97, 13, 27, 49
$ i = 6 $	(13, 38, 49, 65, 76), 97, 27, 49
$ i = 7 $	(13, 27, 38, 49, 65, 76, 97), 49
$ i = 8 $	(13, 27, 38, 49, 49, 65, 76, 97) 完成排序

括号内表示当前已排序的子序列。

性能分析：

空间复杂度：只使用了常数个辅助单元，因此空间复杂度为 $ O(1) $。
时间复杂度：
- 最好情况：如果序列已经有序，每次只需要比较一次，不需要移动元素，时间复杂度为 $ O(n) $。
- 最坏情况：如果序列是逆序，则每次插入时都要将所有前面的元素向后移动，比较和移动次数最大，时间复杂度为 $ O(n^2) $。
在直接插入排序的最坏情况下，表中元素是逆序排列的，即每次都需要将新元素插入到已有序列的最前面。此时，比较次数和移动次数都达到最大值。

最坏情况下的比较次数：

对于每个元素 $ L[i] $，它需要与前面已经排好序的 $ i-1 $ 个元素进行比较，直到找到它的插入位置。由于表是逆序的，因此每次插入时需要比较 $ i-1 $ 次。总的比较次数可以表示为： $ = 1 + 2 + 3 + + (n-1) = _{i=1}^{n-1} i = $ 这是一个等差数列，其和为： $ $

最坏情况下的移动次数：

在逆序的情况下，每次插入元素都需要将所有前面的 $ i-1 $ 个元素向后移动，因此第 $ i $ 次插入需要移动 $ i $ 次（包括最后的插入操作）。总的移动次数可以表示为： $ = 2 + 3 + 4 + + n = _{i=2}^{n} i = - 1 $ 这个公式的解释如下：
- 第一次插入只需移动 1 个元素。
- 第二次插入需要移动 2 个元素，以此类推。因此，总的移动次数为 $ - 1 $。
- 平均情况：考虑序列元素是随机排列的，总的比较和移动次数均约为 $ O(n^2) $。
稳定性：直接插入排序是稳定的排序方法，因为相同元素的相对位置不会发生变化。

适用性：

直接插入排序适用于顺序存储和链式存储的线性表。在链式存储的情况下，也可以从前往后查找指定元素的位置。

折半插入排序

折半插入排序是对直接插入排序的一种改进。它的核心思想是将比较和移动操作分离。通过折半查找来确定待插入元素的位置，而不是直接从前向后顺序查找位置。折半插入排序的具体过程包括以下两步：

折半查找：通过折半查找的方法确定插入位置。
统一移动元素：确定插入位置后，统一地移动插入位置之后的元素，然后插入待排序元素。

折半插入排序可以大大减少比较次数，因为每次查找插入位置时使用了折半查找，比较次数减少到 $ O(n n) $。但是，由于插入操作仍然需要统一地移动元素，因此移动次数并没有改变，依然与直接插入排序相同。

折半插入排序的代码实现：

void BinaryInsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; ++i) {  // 从第二个元素开始逐个插入
        A[0] = A[i];  // 将待插入的元素暂存在 A[0]
        low = 1;
        high = i - 1;  // 设置折半查找的范围为 [1, i-1]

        // 折半查找确定插入位置
        while (low <= high) {
            mid = (low + high) / 2;  // 取中间点
            if (A[mid] > A[0])
                high = mid - 1;  // 查找左半子表
            else
                low = mid + 1;   // 查找右半子表
        }

        // 统一后移元素，空出插入位置
        for (j = i - 1; j >= high + 1; --j) {
            A[j + 1] = A[j];
        }
        // 插入操作
        A[high + 1] = A[0];
    }
}

算法分析：

比较次数：折半插入排序使用折半查找来寻找插入位置，因此在每次插入时，比较次数减少到 $ O(n) $。总的比较次数大约为：$ O(n n) $ 这与待排序表的初始状态无关，仅取决于元素的个数。
移动次数：虽然折半插入排序减少了比较次数，但元素的移动次数并没有改变，仍然需要将插入位置后的所有元素统一向后移动。移动次数与直接插入排序相同，在最坏情况下依然为 $ O(n^2) $，取决于初始状态。
时间复杂度：
- 最好情况下：当序列已经有序时，插入元素只需比较，不需要移动，时间复杂度为 $ O(n n) $。
- 最坏情况下：当序列逆序时，比较次数为 $ O(n n) $，但移动次数达到最大值，时间复杂度仍然为 $ O(n^2) $。
- 平均情况下：比较次数为 $ O(n n) $，移动次数为 $ O(n^2) $，总的时间复杂度为 $ O(n^2) $。
空间复杂度：折半插入排序是就地排序算法，使用了常数个辅助单元，因此空间复杂度为 $ O(1) $。
稳定性：折半插入排序是稳定的排序算法，因为在插入过程中，如果待插入的元素与有序子序列中的某个元素相等，它会插入到该元素之后，保持了稳定性。

希尔排序

希尔排序（Shell Sort）是对直接插入排序的改进，目的是提升排序效率，尤其是在处理数据量较大且无序度较高的情况下。希尔排序又称为缩小增量排序，它的基本思想是：通过将序列分割成若干个子序列进行排序，使整个序列逐渐趋于有序，再对整体进行一次直接插入排序。希尔排序通过逐步减少增量，最终使排序效率得以提升。

基本思想：

希尔排序通过逐步缩小数据间的比较间隔（称为增量，通常用 $d$ 表示），将待排序的序列分成多个子序列，分别对这些子序列进行插入排序。每趟排序结束后，逐渐缩小增量 $d$，直到 $d=1$，再进行最后一趟插入排序。这种方式使得在后期排序时，待排序列已经基本有序，从而提升排序效率。

希尔排序的过程：

初始增量 $d = n/2$：将序列分为若干个子序列，对这些子序列分别进行直接插入排序。
逐步缩小增量：每一趟排序后，缩小增量 $d$，重复子序列的排序过程，直到 $d = 1$。
最后一趟：当增量为 1 时，对整个序列进行插入排序。

以下是一个增量变化过程的示例：

初始关键字序列： $ 13 27 49 38 65 97 55 04 76 16 $
第一趟排序（增量 $d = 5$）：对下标分别为 0, 5，1, 6，2, 7 等分组，进行直接插入排序，排序后的序列为： $ 13 27 49 38 65 16 55 04 76 97 $
第二趟排序（增量 $d = 3$）：对下标分别为 0, 3, 6, 9，1, 4, 7，2, 5, 8 分组，进行插入排序，排序后的序列为： $ 13 16 49 04 27 55 38 65 76 97 $
最后一趟排序（增量 $d = 1$）：对整个序列进行一次插入排序，最终得到有序序列： $ 04 13 16 27 38 49 55 65 76 97 $

希尔排序算法的代码实现：

void ShellSort(ElemType A[], int n) {
    int i, j, dk;
    // 步长逐步减小
    for (dk = n / 2; dk >= 1; dk = dk / 2) {
        // 从第 dk + 1 个元素开始逐个插入
        for (i = dk + 1; i <= n; ++i) {
            if (A[i] < A[i - dk]) {
                A[0] = A[i];  // 暂存待插入元素
                for (j = i - dk; j > 0 && A[0] < A[j]; j -= dk) {
                    A[j + dk] = A[j];  // 元素后移
                }
                A[j + dk] = A[0];  // 插入到正确位置
            }
        }
    }
}

希尔排序的性能分析：

空间复杂度：
- 希尔排序只使用了常数个辅助单元，因此空间复杂度为 $ O(1) $。
时间复杂度：
- 希尔排序的时间复杂度依赖于增量序列的选择，目前尚未找到最优的增量序列。常见的增量选择方式有：
  - 希尔增量（$ d = n/2, d = d/2, , 1 $）：在最坏情况下，时间复杂度为 $ O(n^2) $。
  - Hibbard 增量：时间复杂度为 $ O(n^{3/2}) $。
  Hibbard 增量是一种用于 希尔排序 的增量序列策略，旨在提高排序效率。它的增量序列形式为： $ d_k = 2^k - 1 $，即增量依次为 1, 3, 7, 15, 31, 63, ... 这些是形如 $ 2^k - 1 $ 的数字。
  
  Hibbard 增量序列的核心思想是选择不太大的增量序列，使得在进行插入排序时，可以逐步缩小序列的无序度，从而减少移动和比较次数。
  - Sedgewick 增量：时间复杂度可以达到 $ O(n^{4/3}) $。
  Sedgewick 增量是由计算机科学家 Robert Sedgewick 提出的用于 希尔排序 的一种增量序列，用来进一步优化排序性能。Sedgewick 增量序列被认为在许多情况下可以优于其他增量序列，如简单的 $ d = n/2 $ 或 Hibbard 增量。
  
  Sedgewick 增量序列的形式：
  
  Sedgewick 提出的增量序列是根据两种不同的公式生成的：
  1. $ 9 ^i - 9 ^i + 1 $ （奇数项）
  2. $ 4^i - 3 ^i + 1 $ （偶数项）
  通过这两个公式，Sedgewick 增量生成了这样的一些增量值：
  - $ 1, 5, 19, 41, 109, 209, 505, 929, $
  Sedgewick 增量的特点：
  1. 高效性：相比于希尔最初的增量序列（$ d = n/2 $）或 Hibbard 增量，Sedgewick 增量序列通常表现得更好，尤其是在大规模数据集上。其最坏情况下的时间复杂度约为 $ O(n^{4/3}) $，比 Hibbard 增量的 $ O(n^{3/2}) $ 更优。
  2. 不稳定性：同样，Sedgewick 增量的希尔排序是一种不稳定的排序算法，因为它可能会在分组排序的过程中打乱相同关键字元素的相对顺序。
  3. 适用性：与 Hibbard 增量类似，Sedgewick 增量适用于顺序存储的线性表（数组），且在面对大规模数据时性能较优。
  Sedgewick 增量的生成：
  - 第一个公式（奇数项）：$ 9 ^i - 9 ^i + 1 $ 生成较大的增量序列。
    - 例如，当 $ i = 0 $ 时，生成的增量为 $ 9 ^0 - 9 ^0 + 1 = 1 $
    - 当 $ i = 1 $ 时，生成的增量为 $ 9 ^1 - 9 ^1 + 1 = 19 $
  - 第二个公式（偶数项）：$ 4^i - 3 ^i + 1 $ 生成较小的增量序列。
    - 例如，当 $ i = 1 $ 时，生成的增量为 $ 4^1 - 3 ^1 + 1 = 5 $
    - 当 $ i = 2 $ 时，生成的增量为 $ 4^2 - 3 ^2 + 1 = 41 $
- 在大多数实际应用中，希尔排序的时间复杂度约为 $ O(n^{1.3}) $，且表现优于直接插入排序。
稳定性：
- 希尔排序是不稳定的排序算法。当两个相同关键字的记录被划分到不同的子表时，它们之间的相对顺序可能会发生变化。例如，在排序过程中，两个值为 49 的元素可能在排序后顺序发生改变。
适用性：
- 希尔排序适用于顺序存储的线性表，尤其是数据量较大且初始无序的情况下，希尔排序能提供比直接插入排序更高的效率。