希尔排序。

一、希尔排序简介

希尔排序是插入排序的一种高效改进版本，也称为"缩小增量排序"（Diminishing Increment Sort）。它由D.L.Shell于1959年提出，是直接插入排序算法的优化版本。

特点：

• 非稳定排序算法（相同元素的相对位置可能改变）
• 时间复杂度：平均O(n^1.3)，最坏O(n^2)
• 空间复杂度：O(1)（原地排序）

二、希尔排序基本原理

希尔排序的核心思想是：将待排序的序列按照一定的"增量"（gap）分成若干个子序列，对每个子序列分别进行插入排序。然后逐渐减小增量，重复这个过程，直到增量为1时，整个序列基本有序，最后进行一次插入排序完成排序。

为什么有效？

1. 插入排序在处理几乎有序的数据时效率很高（接近O(n)）
2. 但插入排序每次只能移动一位，效率较低
3. 希尔排序通过"大步长"排序，使数据快速接近有序状态，再用小步长进行精细调整

三、希尔排序的步骤

1. 选择一个增量序列（通常从n/2开始，每次减半，直到1）
2. 按照当前增量，将数组分成若干组
3. 对每组进行直接插入排序
4. 缩小增量，重复步骤2-3
5. 当增量为1时，整个数组基本有序，进行一次插入排序完成排序

四、实现

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    // 初始增量为数组长度的一半
    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[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    shellSort(arr, n);
    
    printf("希尔排序后：");
    printArray(arr, n);
    
    return 0;
}

五、代码详解

1. 增量序列的确定

for (int gap = n / 2; gap > 0; gap /= 2)

• 初始增量取数组长度的一半（n/2）
• 每次循环后，增量减半（gap /= 2）
• 直到增量变为0（当n=1时，gap=0.5，整数除法后为0）

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;
}

• 从第一个增量位置开始遍历
• 将当前元素与前面的元素比较（间隔为gap）
• 将比当前元素大的元素向后移动
• 找到合适位置后插入当前元素

六、希尔排序示例（详细步骤）

假设待排序数组：[49, 38, 65, 97, 76, 13, 27, 49, 55, 4]

初始增量：gap = 10/2 = 5

第一轮（gap=5）：

将数组分成5个子序列：

• 子序列1: [49, 13] → 排序后: [13, 49]
• 子序列2: [38, 27] → 排序后: [27, 38]
• 子序列3: [65, 49] → 排序后: [49, 65]
• 子序列4: [97, 55] → 排序后: [55, 97]
• 子序列5: [76, 4] → 排序后: [4, 76]

排序后数组：[13, 27, 49, 55, 4, 49, 38, 65, 97, 76]

第二轮（gap=2）：

将数组分成2个子序列：

• 子序列1: [13, 49, 4, 65, 97] → 排序后: [4, 13, 49, 65, 97]
• 子序列2: [27, 55, 49, 38, 76] → 排序后: [27, 38, 49, 55, 76]

排序后数组：[4, 27, 13, 38, 49, 49, 55, 65, 97, 76]

第三轮（gap=1）：

整个数组进行一次插入排序，得到最终有序数组： [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

七、希尔排序特点

优点：

1. 比直接插入排序效率高，尤其在数据量较大时
2. 原地排序，空间复杂度低（O(1)）
3. 实现相对简单

缺点：

1. 非稳定排序算法
2. 增量序列的选择对性能影响较大
3. 最坏情况时间复杂度仍为O(n^2)