希尔排序：突破传统排序的边界

一、算法思想

希尔排序（Shell Sort），也被叫做缩小增量排序，是插入排序的一种改进版本。希尔排序的核心在于先将整个待排序的记录序列分割成若干个子序列，分别进行直接插入排序。随着增量逐渐减小，子序列的长度慢慢增加，整个序列会变得越来越接近有序。当增量减至 1 时，整个序列就会被合并为一个，再进行一次直接插入排序，最终完成整个排序过程。

与插入排序对比

插入排序在处理部分有序的数组时效率更高，而希尔排序正是利用了这一特性。它通过分组预排序，让数组先达到部分有序的状态，最后再进行一次插入排序，从而减少了元素移动的次数。

算法步骤

1. 选择增量序列：确定一个递减的增量序列，常用的增量序列有希尔增量（n/2, n/4, ..., 1）、Knuth 增量（3k +1）等。
2. 按增量分组：根据当前增量将数组分成若干个子序列，每个子序列的元素间隔为当前增量。
3. 对子序列排序：对每个子序列分别进行插入排序。
4. 减小增量：增量逐渐减小，重复步骤 2 和 3，直到增量为 1。
5. 最终排序：当增量为 1 时，整个数组作为一个子序列进行一次插入排序，此时数组已基本有序，插入排序效率较高。

二、手动排序示例

下面以数组 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例，详细展示希尔排序的过程。这里我们采用希尔增量序列（初始增量为数组长度的一半，之后每次减半）。

初始数组

[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]

第一趟排序（增量为 5）

将数组分成 5 个子序列：

• 子序列 1：[8, 3] → 排序后 [3, 8]
• 子序列 2：[9, 5] → 排序后 [5, 9]
• 子序列 3：[1, 4] → 排序后 [1, 4]
• 子序列 4：[7, 6] → 排序后 [6, 7]
• 子序列 5：[2, 0] → 排序后 [0, 2]

排序后的数组：

[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

第二趟排序（增量为 2）

将数组分成 2 个子序列：

• 子序列 1：[3, 1, 0, 9, 7] → 排序后 [0, 1, 3, 7, 9]
• 子序列 2：[5, 6, 8, 4, 2] → 排序后 [2, 4, 5, 6, 8]

排序后的数组：

[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

第三趟排序（增量为 1）

此时进行直接插入排序：

[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] → [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

最终得到有序数组：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

三、C 语言实现代码

下面是希尔排序的 C 语言实现，采用希尔增量序列：

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    // 初始增量为数组长度的一半，之后每次减半，直到增量为1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            // 插入排序逻辑：将当前元素插入到其所在子序列的正确位置
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

// 打印数组函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数
int main() {
    int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: \n");
    printArray(arr, n);

    shellSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

四、代码解释

希尔排序函数 shellSort

1. 增量序列控制：

   • 初始增量 gap 设为数组长度的一半（n/2）。
   • 每轮循环后将增量减半（gap /= 2），直到增量为 1。

2. 分组插入排序：

   • 对于每个增量 gap，将数组分为 gap 个子序列。
   • 对每个子序列进行插入排序，确保元素在各自子序列中有序。

3. 插入排序优化：

   • 使用临时变量 temp 保存当前元素。
   • 通过比较和移动元素，找到 temp 应插入的位置。

主函数 main

1. 数组初始化：定义待排序的数组 arr。
2. 排序前输出：调用 printArray 函数显示原始数组。
3. 调用排序：调用 shellSort 函数对数组进行排序。
4. 排序后输出：再次调用 printArray 函数显示排序后的数组。

五、算法复杂度与稳定性

时间复杂度

希尔排序的时间复杂度与增量序列的选择有关，不同的增量序列会导致不同的时间复杂度：

• 最坏情况：希尔增量序列下为 O (n²)
• 平均情况：取决于增量序列，可能达到 O (n^1.3) 或更好
• 最好情况：当数组已经有序时为 O (n)

空间复杂度

希尔排序只需要常数级的额外空间，因此空间复杂度为 O (1)。

稳定性

希尔排序是一种不稳定的排序算法，因为在不同的子序列插入排序过程中，相同元素的相对顺序可能会发生改变。

六、希尔排序的优缺点

优点

1. 高效性：对于中等规模的数据，希尔排序的性能通常优于直接插入排序和选择排序。
2. 空间效率：只需要常数级的额外空间。
3. 实现简单：代码结构相对简单，易于理解和实现。

缺点

1. 复杂度分析困难：时间复杂度依赖于增量序列的选择，难以精确分析。
2. 不稳定性：不适合需要保持元素相对顺序的应用场景。

七、适用场景

希尔排序适用于以下场景：

• 数据量中等且不需要稳定性的排序任务。
• 对内存使用有限制的环境，因为它只需要 O (1) 的额外空间。
• 作为更复杂排序算法的预处理步骤。

希尔排序通过巧妙的分组策略，打破了传统插入排序的性能瓶颈，为排序算法的发展开辟了新的思路。在实际应用中，合理选择增量序列可以显著提高希尔排序的性能。