C、算法 152°C 30-12-2024

^{最近更新于：2025-03-06 17:13:31}

希尔排序（Shell Sort）是一种基于插入排序的排序算法，也是第一种突破 O(n²) 时间复杂度的算法，由 Donald Shell 于 1959 年提出。希尔排序通过将数组分成若干个子序列，对每个子序列进行插入排序，逐渐减少子序列间的间隔，最终完成排序。

核心思想

希尔排序的核心思想是：先让数组中任意间隔为 h 的元素组成一个子序列，对这些子序列分别进行插入排序，逐步缩小间隔 h ，直到 h = 1 ，此时整个数组变为一个普通的插入排序。

通过逐渐缩小间隔，希尔排序能够让数据在全局范围上更加接近最终有序状态，从而减少了插入排序中数据移动的次数。

算法步骤

确定初始间隔 h
通常选择 h = n/2（数组长度的一半），然后逐步缩小为 h = h/2 ，直到 h = 1 。
分组
按照当前间隔 h ，将数组分为若干子序列。例如，间隔为 h 时，数组中的索引为 0, h, 2h, 3h, … 的元素属于同一个子序列。
对每个子序列进行插入排序
在每一轮间隔 h 下，对每个子序列进行插入排序。
缩小间隔 h
将间隔 h 缩小，重复步骤 2 和 3，直到 h = 1 。
完成排序
最后一轮 h = 1 就是一个普通的插入排序，此时数组已经接近有序，插入排序效率会更高。

示例讲解

例1

假设要排序的数组是：

[ 50, 26, 38, 80, 70, 90, 8, 30, 40, 20]

第一轮：步长 h = 5

按间隔 h = 5 分组，每组包含间隔为 5 的元素：

第 1 组：[50, 90]
第 2 组：[26, 8]
第 3 组：[38, 30]
第 4 组：[80, 40]
第 5 组：[70, 20]

对每组进行插入排序：

第 1 组：[50, 90] → 已经有序
第 2 组：[26, 8] → 排序后：[8, 26]
第 3 组：[38, 30] → 排序后：[30, 38]
第 4 组：[80, 40] → 排序后：[40, 80]
第 5 组：[70, 20] → 排序后：[20, 70]

排序后的数组：

[ 50, 8, 30, 40, 20, 90, 26, 38, 80, 70 ]

第二轮：步长 h = 3

按间隔 h = 3 分组，每组包含间隔为 3 的元素：

第 1 组：[50, 40, 26, 70]
第 2 组：[8, 20, 38]
第 3 组：[30, 90, 80]

对每组进行插入排序：

第 1 组：[50, 40, 26, 70] → 排序后：[26, 40, 50, 70]
第 2 组：[8, 20, 38] → 已经有序
第 3 组：[30, 90, 80] → 排序后：[30, 80, 90]

排序后的数组：

[ 26, 8, 30, 40, 20, 80, 50, 38, 70, 90 ]

第三轮：步长 h = 1

步长 h = 1 表示整个数组进行插入排序：

插入 8：[26, 8, 30, 40, 20, 80, 50, 38, 70, 90] → [8, 26, 30, 40, 20, 80, 50, 38, 70, 90]
插入 30：[8, 26, 30, 40, 20, 80, 50, 38, 70, 90] → 已经有序
插入 40：[8, 26, 30, 40, 20, 80, 50, 38, 70, 90] → 已经有序
插入 20：[8, 26, 30, 40, 20, 80, 50, 38, 70, 90] → [8, 20, 26, 30, 40, 80, 50, 38, 70, 90]
插入 80：[8, 20, 26, 30, 40, 80, 50, 38, 70, 90] → 已经有序
插入 50：[8, 20, 26, 30, 40, 80, 50, 38, 70, 90] → [8, 20, 26, 30, 40, 50, 80, 38, 70, 90]
插入 38：[8, 20, 26, 30, 40, 50, 80, 38, 70, 90] → [8, 20, 26, 30, 38, 40, 50, 80, 70, 90]
插入 70：[8, 20, 26, 30, 38, 40, 50, 80, 70, 90] → [8, 20, 26, 30, 38, 40, 50, 70, 80, 90]
插入 90：[8, 20, 26, 30, 38, 40, 50, 70, 80, 90] → 已经有序

最终排序结果：

[ 8, 20, 26, 30, 38, 40, 50, 70, 80, 90 ]

总结排序过程：

步长 5：让数组“局部有序”。
步长 3：进一步减少无序范围。
步长 1：最终通过插入排序完成排序。

例2

假设要排序的数组是：

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

1. 初始状态

数组长度 n = 10 ，初始间隔 h = n / 2 = 5 。

分组：每隔 5 个元素分为一组

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

对每组分别进行插入排序：

第 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. 缩小间隔

将间隔缩小为 h = 5 / 2 = 2 。

分组：每隔 2 个元素分为一组

第 1 组：[3, 1, 0, 9, 7]
第 2 组：[5, 6, 8, 4, 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, 8, 9]

3. 缩小间隔

将间隔缩小为 h = 2 / 2 = 1 （即普通插入排序）。

整个数组视为一个序列，进行插入排序：

插入 2：[0, 2, 1, 4, 3, 5, 7, 6, 8, 9]（2 已在正确位置）
插入 1：[0, 1, 2, 4, 3, 5, 7, 6, 8, 9]
插入 4：[0, 1, 2, 4, 3, 5, 7, 6, 8, 9]（4 已在正确位置）
插入 3：[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
插入 5：[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]（5 已在正确位置）
插入 7：[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]（7 已在正确位置）
插入 6：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
插入 8：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]（8 已在正确位置）
插入 9：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]（9 已在正确位置）

4. 排序完成

最终数组为：

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

总结过程

第一步：按间隔 5 排序，数组变得“局部有序”。
第二步：按间隔 2 排序，数组进一步接近有序。
第三步：按间隔 1 排序（普通插入排序），完成最终排序。

参考代码

#include <stdio.h>

// 希尔排序函数
void shellSort(int arr[], int n) {
    // 初始步长 h 为 n/2，每次循环后步长减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 从 gap 开始，将每个元素插入到对应的分组中
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 暂存当前元素
            int j;
            // 通过步长 gap 比较并将元素向后移动
            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[] = {50, 26, 38, 80, 70, 90, 8, 30, 40, 20};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    shellSort(arr, n);

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

    return 0;
}

输出结果

运行代码的输出如下：

原始数组: 50 26 38 80 70 90 8 30 40 20 
排序后数组: 8 20 26 30 38 40 50 70 80 90

代码分析

1. void shellSort(int arr[], int n)

这是希尔排序的主函数，实现了排序功能。其核心思想是：

使用一个外层循环控制步长（gap）的减小。
使用一个嵌套循环对每组数据进行插入排序。

关键细节：

步长控制：for (int gap = n / 2; gap > 0; gap /= 2)
- 初始步长为数组长度的一半，每次循环后步长减半，直到步长为 1。
- 间隔减少的过程可以看作分组逐渐合并的过程。
分组插入排序：for (int i = gap; i < n; i++)
- 从索引 gap 开始，将每个元素插入到当前分组的正确位置。
- 通过内部循环 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)，比较并将大于 temp 的元素向后移动，为 temp 腾出插入位置。
核心移动逻辑：
- 使用 temp 暂存当前元素值。
- 内循环中，逐步将分组中较大的元素向后移动，直到找到正确插入位置。
时间复杂度：
- 最坏情况：O(n²)，步长序列选取不当时接近插入排序。
- 平均情况：O(n^1.3)（取决于步长序列优化）。

2. void printArray(int arr[], int n)

该函数用于打印数组的内容。其功能是：

遍历数组，通过 printf 输出每个元素。
用空格分隔元素，最后输出换行符。

运行逻辑

假设初始数组为：[50, 26, 38, 80, 70, 90, 8, 30, 40, 20]

第一轮：gap = 5
- 分组：[50, 90], [26, 8], [38, 30], [80, 40], [70, 20]
- 插入排序结果：[50, 26, 38, 80, 70, 90, 8, 30, 40, 20]
  - 排序后：[50, 8, 30, 40, 20, 90, 26, 38, 80, 70]
第二轮：gap = 3
- 分组：[50, 40, 26, 70], [8, 20, 38], [30, 90, 80]
- 插入排序结果：[26, 40, 50, 70], [8, 20, 38], [30, 80, 90]
  - 排序后：[26, 8, 30, 40, 20, 80, 50, 38, 70, 90]
第三轮：gap = 1
- 整体插入排序，逐步调整位置。
  - 最终结果：[8, 20, 26, 30, 38, 40, 50, 70, 80, 90]

时间复杂度

希尔排序的时间复杂度与选取的间隔序列有关。常见的间隔序列有：

h = n/2, n/4, … , 1（简单间隔序列）
Hibbard 序列：h_k = 2^k – 1
Knuth 序列：h_k = 3^k – 1 / 2

时间复杂度（平均情况）通常在 O(n^1.3) 到 O(n^1.5) 之间，最优情况可以接近 O(n log n) 。

优点与缺点

优点：

比普通插入排序效率高，尤其对于大规模数组。
算法实现简单，空间复杂度低 O(1) 。

缺点：

性能受间隔序列选择影响，缺乏统一标准。
对非常大的数据集来说，性能不如高级排序算法（如归并排序或快速排序）。

评论留言

欢迎您，！您可以在这里畅言您的的观点与见解！

0 条评论

希尔排序