希尔排序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 < n; i++) {
                // 保存当前元素
                int temp = arr[i];
                int j;
                
                // 对同一组的元素进行插入排序
                for (j = i; j >= 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 < array2.length ; i++) {
         int tmp = array2[i];//tmp存放i下标的值
         int j = i - gap;//j下标为i-gap个位置
         //j每次-gap个位置
         for (; j >= 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 < n/3) {
        h = 3*h + 1;
    }
    
    // 使用Knuth序列进行希尔排序
    while (h >= 1) {
        // 对每个步长进行插入排序
        for (int i = h; i < n; i++) {
            int temp = arr[i];
            int j;
            
            for (j = i; j >= 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 < n) {
        k++;
    }
    k--;
    
    // 使用Hibbard序列进行希尔排序
    while (k >= 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 <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > 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)等 亚二次时间复杂度。