希尔排序

算法定义

希尔排序（Shell Sort）是插入排序的一种改进版本，由计算机科学家希尔（Donald Shell）在 1959 年提出。它通过将数组按一定间隔（步长）分为多个子数组，对每个子数组进行插入排序，然后逐步缩小间隔，重复上述过程，直到间隔为 1，最后进行一次普通插入排序，使整个数组有序。

希尔排序的核心思想是让元素先进行远距离的交换，使数组尽快基本有序，再进行近距离交换（最终为相邻元素），从而克服插入排序在处理大规模无序数组时效率低下的问题。

算法思路

希尔排序的步骤如下：

选择初始步长：通常选择数组长度的一半（gap = n/2）作为初始步长。
分组插入排序：按当前步长gap将数组分为gap个子数组，对每个子数组执行插入排序。
缩小步长：将步长缩小（通常取当前步长的一半，gap = gap/2），重复步骤 2。
终止条件：当步长缩小到 1 时，进行最后一次插入排序（此时就是普通插入排序），排序完成。

不同的步长选择会影响希尔排序的效率，常见的步长序列有希尔初始步长（n/2, n/4, ..., 1）、Knuth 步长（(3^k - 1)/2）等。

算法复杂度

最好时间复杂度：O (n log n) - 取决于步长序列，部分优化步长可达到此复杂度
最坏时间复杂度：O (n²) - 采用希尔初始步长时；优化步长可降至 O (n^1.5) 或更低
平均时间复杂度：O (n log n) ~ O (n²) - 取决于步长序列，目前尚无精确结论
空间复杂度：O (1) - 原地排序，只需常数级额外空间

优点与缺点

优点：
- 比普通插入排序效率高，尤其对中等规模数组
- 原地排序，空间复杂度低（O (1)）
- 实现简单，易于理解和编码
- 对几乎有序的数组效率更高
缺点：
- 不稳定的排序算法（相等元素的相对位置可能改变）
- 性能依赖步长序列的选择，不同步长效率差异大
- 理论分析复杂，时间复杂度难以精确证明
- 对大规模数据，效率不如快速排序、归并排序等 O (n log n) 级算法

应用场景

中等规模数据的排序（比插入排序适合更大规模数据）
对空间使用有严格限制的场景（原地排序特性）
嵌入式系统或内存有限的设备
作为其他复杂排序算法的补充（如处理部分有序数组）

各版本优化说明

基本版（希尔步长）：
- 采用希尔提出的初始步长（n/2, n/4, ..., 1）
- 实现简单，但步长之间存在倍数关系，可能导致某些元素重复比较
- 最坏时间复杂度为 O (n²)
Knuth 步长优化：
- 使用 Knuth 提出的步长序列：(3^k - 1)/2（如 1, 4, 13, 40, 121...）
- 步长之间不成倍数关系，减少了重复比较
- 最坏时间复杂度优化至 O (n^1.5)，适合中等规模数组
Sedgewick 步长优化：
- 使用 Sedgewick 提出的复合步长序列（如 1, 5, 19, 41...）
- 经过严格测试，在实践中表现最优，平均时间复杂度接近 O (n log n)
- 适合较大规模数组，但步长序列需要预先定义
混合插入排序优化：
- 当步长缩小到某个阈值（如 15）时，改用普通插入排序
- 利用插入排序在小规模数据上的高效性，减少希尔排序的迭代次数
- 综合性能优于纯希尔排序，实现简单且实用

希尔排序是插入排序的高效改进版，通过合理选择步长序列，可以在中等规模数据排序中获得良好性能。它的实现简单且空间开销小，是实际应用中值得考虑的排序算法。

代码

import java.util.Arrays;

public class ShellSort {
    
    // 1. 基本版希尔排序（希尔初始步长：n/2, n/4, ..., 1）
    public static void shellSortBasic(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        // 步长从n/2开始，每次减半
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子数组进行插入排序
            for (int i = gap; i < n; i++) {
                int key = arr[i]; // 当前待插入元素
                int j = i;
                
                // 子数组内的插入排序（步长为gap）
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap]; // 元素后移
                    j -= gap;
                }
                arr[j] = key; // 插入元素
            }
        }
    }
    
    // 2. 优化版1：Knuth步长序列（(3^k - 1)/2）
    public static void shellSortKnuth(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        int gap = 1;
        
        // 计算最大的Knuth步长（小于n/3）
        while (gap <= n / 3) {
            gap = gap * 3 + 1; // Knuth步长公式：3^k - 1 / 2
        }
        
        // 按Knuth步长排序，逐步减小步长
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
            // 步长减小（反向应用Knuth公式）
            gap = (gap - 1) / 3;
        }
    }
    
    // 3. 优化版2：Sedgewick步长序列（更高效的步长）
    public static void shellSortSedgewick(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        
        // 生成Sedgewick步长序列（适合n < 10^6）
        int[] sedgewickGaps = {1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 
                             16001, 36289, 64769, 146305, 260609};
        
        // 找到适合当前数组长度的最大步长
        int gapIndex = 0;
        while (gapIndex < sedgewickGaps.length && sedgewickGaps[gapIndex] < n) {
            gapIndex++;
        }
        gapIndex--;
        
        // 按Sedgewick步长排序
        while (gapIndex >= 0) {
            int gap = sedgewickGaps[gapIndex];
            
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
            
            gapIndex--;
        }
    }
    
    // 4. 优化版3：对小规模子数组使用插入排序
    public static void shellSortHybrid(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        final int INSERTION_THRESHOLD = 15; // 子数组长度阈值
        
        // 希尔排序主循环
        for (int gap = n / 2; gap > INSERTION_THRESHOLD; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
        
        // 当步长小于阈值时，直接使用插入排序
        if (n > INSERTION_THRESHOLD) {
            insertionSort(arr, 0, n - 1);
        }
    }
    
    // 辅助插入排序（用于混合版本）
    private static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = arr[i];
            int j = i - 1;
            
            while (j >= left && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 5, 1, 8, 7, 6, 4, 3, 2};
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        int[] arr4 = Arrays.copyOf(arr, arr.length);
        
        shellSortBasic(arr1);
        System.out.println("基本版（希尔步长）: " + Arrays.toString(arr1));
        
        shellSortKnuth(arr2);
        System.out.println("Knuth步长: " + Arrays.toString(arr2));
        
        shellSortSedgewick(arr3);
        System.out.println("Sedgewick步长: " + Arrays.toString(arr3));
        
        shellSortHybrid(arr4);
        System.out.println("混合插入排序: " + Arrays.toString(arr4));
    }
}

资料

https://blog.csdn.net/weixin_38333555/article/details/80515605