当前位置：首页 > PHP

php实现希尔排序

2026-02-15 13:03:15PHP

PHP实现希尔排序

希尔排序（Shell Sort）是插入排序的一种高效改进版本，通过将原始数组分割成多个子序列进行插入排序，逐步缩小子序列的间隔直至为1，最终完成排序。

希尔排序算法步骤

选择增量序列
确定一个增量序列（gap sequence），常用的增量序列有希尔原始序列（N/2, N/4, ..., 1）或Knuth序列（1, 4, 13, 40, ...）。
分组插入排序
按照当前增量将数组分为若干子序列，对每个子序列进行插入排序。
逐步缩小增量
重复上述过程，逐步缩小增量直至为1，此时数组基本有序，最后进行一次完整的插入排序。

PHP代码实现

function shellSort(array $arr): array {
    $n = count($arr);
    // 使用希尔原始增量序列（N/2, N/4, ..., 1）
    for ($gap = floor($n / 2); $gap > 0; $gap = floor($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;
}

// 示例用法
$array = [35, 33, 42, 10, 14, 19, 27, 44];
$sortedArray = shellSort($array);
print_r($sortedArray);

代码说明

增量序列：示例中使用希尔原始序列（$gap = floor($n / 2)），每次循环将增量减半。
插入排序：对每个子序列（间隔为$gap的元素）进行插入排序，逐步将较小的元素移动到前面。
时间复杂度：希尔排序的时间复杂度取决于增量序列的选择，平均时间复杂度为O(n log n)，最坏情况下为O(n²)。

优化建议

增量序列选择
使用更高效的增量序列（如Knuth序列）可以进一步提升性能。例如：
```
$gap = 1;
while ($gap < $n / 3) {
    $gap = $gap * 3 + 1;
}
```
边界检查
添加对空数组或单元素数组的检查，避免不必要的计算。
类型安全
确保输入为数组类型，可通过is_array()验证。