# 希尔排序（Shell Sort）

URL: https://caijiao.org/sort/4-shell-sort
Source: docs/sort/4-shell-sort.md
Description: 介绍希尔排序的原理和分组插入策略，适用于中等规模数据。附带 JavaScript、Python、C++、Java、PHP、Go 多语言实现代码，助你深入理解。

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

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

## 📌 算法原理解释

希尔排序的核心思想是：

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 希尔排序
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)（原地排序）                          |
| 稳定性    | ❌ 不稳定                               |
| 是否原地排序 | ✅ 是                                 |

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