希尔排序cc

希尔排序

希尔排序是插入排序的改进版本，通过比较相距一定间隔的元素来工作，逐步减小间隔直到只比较相邻元素。

时间复杂度:最佳 O(n log n) | 平均 O(n log² n) | 最差 O(n²)

空间复杂度:O(1)

稳定性:不稳定

应用场景/前提条件

• 插入排序的改进版
• 适用于中等规模数据

算法讲解

介绍

        希尔排序（Shell Sort）是插入排序的一种改进版本，它是第一个突破O(n²)的排序算法，核心思想是利用步长序列对数据进行分组，在每个分组内使用插入排序，逐步减小步长直到为1，完成最终排序。

        希尔排序时元素会大跨度移动，解决了 插入排序 在处理大规模乱序数组  效率低下的问题，让元素更快移动到正确位置。

算法步骤

1. 选择一个步长序列，建议初始步长 n/2，每次减半直到步长为1
2. 对每个步长，对数组进行分组，对应位置相隔为步长的元素视为一组
3. 对每一组使用  插入排序  进行排序
4. 减小步长，重复步骤2和3，直到步长减少到1
5. 当步长为1时，相当于对整个数组做一次插入排序，此时数组已基本有序，所需的比较和移动次数大大减少

为了帮助大家更好的理解，我们以初始数组 [8, 9, 1, 7, 2, 6, 3, 5, 4] 为例，查看每一步的详细流程：

1）第一轮排序

• 选择间隔 (Gap): 4 (数组长度9除以2取整)
• 分组: 按照间隔4将数组分为4个子序列。
  • 第1组 (下标0, 4, 8): [8, 2, 4]
  • 第2组 (下标1, 5): [9, 6]
  • 第3组 (下标2, 6): [1, 3]
  • 第4组 (下标3, 7): [7, 5]
• 对每组进行插入排序:
  • [8, 2, 4] 排序后变为 [2, 4, 8]
  • [9, 6] 排序后变为 [6, 9]
  • [1, 3] 排序后变为 [1, 3]
  • [7, 5] 排序后变为 [5, 7]
• 本轮结果: 将排序后的元素放回原位置，数组变为 [2, 6, 1, 5, 4, 9, 3, 7, 8]。

2）第二轮排序

• 缩小间隔 (Gap): 2 (上一间隔4除以2)
• 分组: 此时基于新数组 [2, 6, 1, 5, 4, 9, 3, 7, 8]，按照间隔2分为2个子序列。
  • 第1组 (偶数下标): [2, 1, 4, 3, 8]
  • 第2组 (奇数下标): [6, 5, 9, 7]
• 对每组进行插入排序:
  • [2, 1, 4, 3, 8] 排序后变为 [1, 2, 3, 4, 8]
  • [6, 5, 9, 7] 排序后变为 [5, 6, 7, 9]
• 本轮结果: 将元素放回原位置，数组变为 [1, 5, 2, 6, 3, 7, 4, 9, 8]。此时数组已经比之前更加有序。

3）第三轮排序（最终轮）

• 缩小间隔 (Gap): 1。
• 操作: 当间隔为1时，希尔排序就等同于对整个数组进行一次普通插入排序。
• 排序过程: 对 [1, 5, 2, 6, 3, 7, 4, 9, 8] 进行插入排序。由于数组已基本有序，这次排序的效率非常高。
• 最终排序结果: 数组变为完全有序的 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

核心特性

• 递减步长序列：初始较大步长让元素大幅度移动，后续减小步长微调元素位置
• 分组插入排序：对每个步长形成的分组独立应用插入排序
• 时间复杂度：取决于步长序列，一般在O(n1.3)到O(n2)之间
• 不稳定性：相等元素的相对位置在排序后可能会改变
• 适应性：对于中等大小的数组表现良好

基础实现

public class ShellSort { public static void shellSort(int[] arr) { int n = arr.length; // 初始步长为n/2，每次减半 for (int gap = n/2; gap > 0; gap /= 2) { // 对每个步长进行插入排序 for (int i = gap; i = gap && arr[j - gap] > temp; j -= gap) {  arr[j] = arr[j - gap]; } // 将temp放到正确位置 arr[j] = temp; } } } 

代码

 public static void shellSort(int[] array2) { int gap = array2.length; while (gap > 1) { gap /= 2; shell(array2, gap);//调用直接插入排序方法 } } //实现直接插入排序方法 public static void shell(int[] array2, int gap) { //i下标从第一组的第二个数据开始 for (int i = gap; i = 0; j-=gap) {  if (array2[j] > tmp) { //j下标的值大，将j下标的值放到j变量加上一个gap的位置上 array2[j + gap] = array2[j];  }else {  //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上  break;  } } //此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上 array2[j + gap] = tmp; } }

        希尔排序的核心是通过步长（gap）将数组分成多个子序列，对每个子序列进行插入排序。步长初始较大，逐渐减小，最终当步长为1时，整个数组已经基本有序，最后一轮插入排序效率很高。

优化策略

使用优化的步长序列

Knuth提出的步长序列可以提高希尔排序的性能：

public static void knuthShellSort(int[] arr) { int n = arr.length; // 计算初始步长：Knuth序列 h = 3*h + 1 int h = 1; while (h = 1) { // 对每个步长进行插入排序 for (int i = h; i = h && arr[j - h] > temp; j -= h) { arr[j] = arr[j - h]; } arr[j] = temp; } // 更新步长 h = h/3; }}

Hibbard序列

Hibbard提出的步长序列也是一种常用优化：

public static void hibbardShellSort(int[] arr) { int n = arr.length; // 计算初始步长：Hibbard序列 2^k - 1 int k = 1; while ((1 << k) - 1 = 0) { int gap = (1 << k) - 1; // 对每个步长进行插入排序 // ... 与基本实现相同 ... k--; }}

优缺点

优点

• 比插入排序更高效，尤其是对于大规模乱序数组
• 代码简单，容易实现
• 在中等大小的数组中性能良好
• 对于几乎已排序的数据效率很高
• 不需要额外的空间（原地排序）

缺点

• 不是稳定的排序算法
• 步长序列的选择对性能影响很大
• 时间复杂度分析复杂，依赖于所选的步长序列
• 对于非常大的数据集，其他高级排序算法（如快速排序、堆排序）可能更高效
• 对于非常小的数据集，简单的插入排序可能更高效

应用场景

• 中等规模的数据排序
• 作为更复杂排序算法的预处理步骤
• 数组基本有序但有少数元素错位较远的情况
• 嵌入式系统或资源受限环境中的排序
• 实时系统中需要可预测性能的场景

扩展

结合其他排序算法

        可以将希尔排序与其他排序算法结合使用，例如在最后一轮（gap=1）时使用插入排序的优化版本：

public static void hybridShellSort(int[] arr) { int n = arr.length; // 使用希尔排序进行预处理 for (int gap = n/2; gap > 1; gap /= 2) { // ... 标准希尔排序代码 ... } // 最后一轮使用优化的插入排序 binaryInsertionSort(arr);}public static void binaryInsertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int left = 0; int right = i - 1; // 使用二分查找找到插入位置 while (left  key) { right = mid - 1; } else { left = mid + 1; } } // 将元素后移 for (int j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } // 插入元素 arr[left] = key; }}

测验

1. 希尔排序的时间复杂度取决于什么？
2. 希尔排序相比于插入排序的主要优势是什么？
3. 为什么说希尔排序是第一个突破O(n²)的排序算法？

测验答案

1. 步长序列的选择，不同的步长序列会导致不同的时间复杂度。
2. 能够让元素进行大跨度移动，更快地接近最终位置，特别适合大规模乱序数组。
3. 希尔排序在某些步长序列下可以达到O(n^1.3)等 亚二次时间复杂度。