希尔排序详解（C语言实现高效插入排序优化版）

为什么需要希尔排序？

普通插入排序在处理大规模或逆序数据时效率较低（时间复杂度为 O(n²)）。而希尔排序通过“跳跃式”比较和交换，使数据快速接近有序状态，从而显著提升性能。虽然最坏情况仍是 O(n²)，但在实际应用中通常表现接近 O(n log n)。

希尔排序的核心步骤

1. 选择一个间隔序列（gap sequence），如 n/2, n/4, ..., 1。
2. 按当前 gap 将数组分成若干子序列（每个子序列由相距 gap 的元素组成）。
3. 对每个子序列执行插入排序。
4. 缩小 gap，重复上述过程，直到 gap = 1，此时进行最后一次插入排序。

C语言实现希尔排序

下面是一个完整的 C 语言代码示例，包含详细注释：

// 希尔排序函数void shellSort(int arr[], int n) {    int gap, i, j, temp;    // 初始间隔设为数组长度的一半，逐步缩小至1    for (gap = n / 2; gap > 0; gap /= 2) {        // 对每个子序列进行插入排序        for (i = gap; i < n; i++) {            temp = arr[i];            j = i;            // 在子序列中向前比较并移动元素            while (j >= gap && arr[j - gap] > temp) {                arr[j] = arr[j - gap];                j -= gap;            }            arr[j] = temp;        }    }}// 测试主函数#include <stdio.h>int main() {    int arr[] = {64, 34, 25, 12, 22, 11, 90};    int n = sizeof(arr) / sizeof(arr[0]);    printf("排序前: ");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    shellSort(arr, n);    printf("\n排序后: ");    for (int i = 0; i < n; i++) {        printf("%d ", arr[i]);    }    printf("\n");    return 0;}

运行结果

执行上述代码，输出如下：

排序前: 64 34 25 12 22 11 90 排序后: 11 12 22 25 34 64 90 

总结

希尔排序是一种简单而高效的C语言排序算法，它通过引入“间隔”概念优化了传统插入排序。虽然现代有更高效的算法（如快速排序、归并排序），但希尔排序因其代码简洁、无需额外空间、对中等规模数据表现良好，仍被广泛应用于嵌入式系统或教学场景。

掌握希尔排序不仅能加深你对插入排序优化的理解，也是学习更高级数据结构与算法的重要一步。建议动手敲一遍代码，观察每一步 gap 变化时数组的状态，你会收获更多！