希尔排序

希尔排序（Shell Sort）的基本思想是将待排序的序列分成若干个子表，每个子表通过直接插入排序进行排序。

算法原理

• 核心思想：插入排序的改进版，通过 分组插入排序 逐步缩小间隔，最终使数组整体有序。
  • 分组策略：定义增量序列（如 gap = n/2, gap /= 2, ...），每次对间隔为 gap 的子数组进行插入排序。
  • 最终步骤：当 gap = 1 时，退化为标准插入排序，此时数组已基本有序。
• 特点：
  • 不稳定排序（分组可能破坏相同元素的相对顺序）。
  • 性能优于直接插入排序，适合中等规模数据。

---

时间复杂度

场景	时间复杂度	依赖条件
最好情况	O(n log n)	使用优化的增量序列（如Hibbard）
最坏情况	O(n²)	使用简单增量序列（如n/2）
平均情况	O(n log n) ~ O(n²)	取决于增量序列的选择

---

代码实现

Golang 实现

package main

import "fmt"

func shellSort(arr []int) {
    n := len(arr)
    // 初始间隔设为数组长度的一半，逐步缩小
    for gap := n / 2; gap > 0; gap /= 2 {
        // 对每个子数组进行插入排序
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            // 插入排序逻辑（处理间隔为gap的子数组）
            for ; j >= gap && arr[j - gap] > temp; j -= gap {
                arr[j] = arr[j - gap]
            }
            arr[j] = temp
        }
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    shellSort(arr)
    fmt.Println("Sorted:", arr)  // Output: Sorted: [11 12 22 25 34 64 90]
}

Java 实现

public class ShellSort {
  public static void shellSort(int[] arr) {
    int n = arr.length;
    // 初始间隔设为数组长度的一半，逐步缩小
    for (int gap = n / 2; gap > 0; gap /= 2) {
      // 对每个子数组进行插入排序
      for (int i = gap; i < n; i++) {
        int temp = arr[i];
        int j = i;
        // 插入排序逻辑（处理间隔为gap的子数组）
        for (; j >= gap && arr[j - gap] > temp; j -= gap) {
          arr[j] = arr[j - gap];
        }
        arr[j] = temp;
      }
    }
  }

  public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    shellSort(arr);
    System.out.print("Sorted: ");
    for (int num : arr) {
      System.out.print(num + " ");  // Output: Sorted: 11 12 22 25 34 64 90 
    }
  }
}