希尔排序（Shell Sort）

希尔排序是插入排序的升级版本，通过引入“增量”概念，先对相隔一定距离的元素进行插入排序，再逐步缩小间隔，最后执行普通插入排序，从而提高效率。

适合中等规模数据排序，尤其是部分有序的数据。

📌 算法原理解释

希尔排序的核心思想是：

1. 选定一个初始“间隔 gap”，通常为数组长度的一半。
2. 对数组进行“gap 间隔”的插入排序 —— 即每 gap 个元素组成一组排序。
3. 不断缩小 gap，最终 gap=1 时执行一次标准插入排序。

通过先消除数组中距离较远的逆序对，能显著减少最终插入排序所需的移动次数。

例如对数组 [9, 8, 3, 7, 5, 6, 4, 1]，初始 gap=4，会分组为：

• 第1组: 9, 5
• 第2组: 8, 6
• 第3组: 3, 4
• 第4组: 7, 1

每组独立插入排序后，再缩小 gap 继续处理。

💻 多语言代码实现

javascript

// JavaScript 希尔排序
function shellSort(arr) {
  let n = arr.length;
  for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

python

# Python 希尔排序
def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

cpp

// C++ 希尔排序
#include <vector>
using namespace std;

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

java

// 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;
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}

php

<?php
// PHP 希尔排序
function shellSort(array &$arr): array {
    $n = count($arr);
    for ($gap = intdiv($n, 2); $gap > 0; $gap = intdiv($gap, 2)) {
        for ($i = $gap; $i < $n; $i++) {
            $temp = $arr[$i];
            $j = $i;
            while ($j >= $gap && $arr[$j - $gap] > $temp) {
                $arr[$j] = $arr[$j - $gap];
                $j -= $gap;
            }
            $arr[$j] = $temp;
        }
    }
    return $arr;
}
?>

go

// Go 希尔排序
package main

func shellSort(arr []int) []int {
    n := len(arr)
    for gap := n / 2; gap > 0; gap /= 2 {
        for i := gap; i < n; i++ {
            temp := arr[i]
            j := i
            for j >= gap && arr[j-gap] > temp {
                arr[j] = arr[j-gap]
                j -= gap
            }
            arr[j] = temp
        }
    }
    return arr
}

✅ 算法特点与总结

属性	描述
时间复杂度	平均约 O(n^1.3)，最坏 O(n²)，最好 O(n log n)
空间复杂度	O(1)（原地排序）
稳定性	❌ 不稳定
是否原地排序	✅ 是

提示：希尔排序在现代实际应用中不如快排常用，但仍具教学和理解“增量优化”的参考价值。