重温经典算法——希尔排序

版权声明

• 本文原创作者：谷哥的小弟
• 作者博客地址：http://blog.csdn.net/lfdfhl

基本原理

希尔排序是插入排序的改进版，通过按增量分组并逐步缩小增量实现排序。时间复杂度取决于增量序列，平均约为 O(n log n) 到 O(n^(3/2))，空间复杂度 O(1)，不稳定排序，适合中等规模数据。

代码实现

import java.util.Arrays;public class ShellSort {public static void shellSort(int[] arr) {int n = arr.length;// 使用 Knuth 增量序列（h = 3*h + 1）int h = 1;while (h < n / 3) h = 3 * h + 1; // 计算最大初始增量while (h >= 1) {// 按增量 h 进行插入排序for (int i = h; i < n; i++) {int current = arr[i];int j = i;// 在子数组中反向插入排序while (j >= h && arr[j - h] > current) {arr[j] = arr[j - h];j -= h;}arr[j] = current;}h /= 3; // 缩小增量}}public static void main(String[] args) {int[] arr = {8, 3, 1, 4, 6, 7, 2, 5};shellSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [1, 2, 3, 4, 5, 6, 7, 8]}
}