php 希尔排序法

封面图 • 2025-12-17 • PHP

希尔排序（Shell Sort）是插入排序的一种改进版本，由 Donald Shell 在 1959 年提出。它通过将原始列表分割成多个子序列进行排序，从而减少数据移动的次数，提高排序效率。

### 希尔排序的基本思想：

1. 选择一个间隔（gap）值，将整个列表分成若干个子序列。
2. 对每个子序列进行插入排序。
3. 缩小间隔，重复步骤 1 和 2，直到间隔为 1。
4. 最后对整个列表进行一次插入排序（此时间隔为 1）。

### PHP 实现希尔排序

```php
<?php
function shellSort($arr) {
    $n = count($arr);
    $gap = $n / 2; // 初始间隔

while ($gap > 0) {
        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;
        }
        $gap = (int)($gap / 2); // 缩小间隔
    }

return $arr;
}

// 示例用法
$arr = [64, 34, 25, 12, 22, 11, 90];
echo "原始数组: " . implode(", ", $arr) . "\n";

$sortedArr = shellSort($arr);
echo "排序后数组: " . implode(", ", $sortedArr) . "\n";
?>
```

### 说明：

- `gap` 是每次分组的步长，初始为数组长度的一半。
- 每次循环中，使用插入排序对每个子序列进行排序。
- 当 `gap` 为 1 时，相当于一次普通的插入排序，确保最终结果有序。

### 时间复杂度：

- **最坏情况**：O(n²)（当 gap 选择不当时）
- **平均情况**：O(n^(1.3)) ~ O(n^2)
- **最好情况**：O(n)（当数组已经有序）

### 优点：

- 相比于直接插入排序，希尔排序在处理较大数组时更高效。
- 不需要额外的空间，是原地排序。

如果你有特定需求或想了解其他排序算法，欢迎继续提问！