当前位置：首页 > news >正文

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

news 2025/7/16 11:56:08

一、算法思想

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

与插入排序对比

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

算法步骤

选择增量序列：确定一个递减的增量序列，常用的增量序列有希尔增量（n/2, n/4, ..., 1）、Knuth 增量（3k +1）等。
按增量分组：根据当前增量将数组分成若干个子序列，每个子序列的元素间隔为当前增量。
对子序列排序：对每个子序列分别进行插入排序。
减小增量：增量逐渐减小，重复步骤 2 和 3，直到增量为 1。
最终排序：当增量为 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) {// 初始增量为数组长度的一半，之后每次减半，直到增量为1for (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;
}