希尔排序是插入排序的改进版，通过动态缩小增量（gap）分组进行插入排序，PHP 8.1 中推荐用 intdiv() 安全整除，初始 gap 取 floor(n/2)，逐步减半至 1，时间复杂度平均为 O(n^1.3)～O(n^1.5)，非稳定排序。
PHP 8.1 中实现希尔排序，核心是分组插入排序 + 动态缩小增量。它不是简单地套用冒泡或快排逻辑，而是通过设定间隔（gap），将数组分成若干子序列，对每个子序列做插入排序；再逐步缩小 gap，直到为 1，最终完成整体有序。
希尔排序原理与关键点
希尔排序是插入排序的改进版，解决插入排序在大规模乱序数据中移动次数过多的问题。关键在于：
- 初始 gap 通常取 floor(n / 2)，之后每次 gap = floor(gap / 2)，直到 gap == 1
- 每轮按当前 gap 将数组“逻辑分组”：索引为 i, i+gap, i+2gap… 的元素属同一组
- 对每组单独做插入排序（即跨步长比较与后移）
- PHP 8.1 中可放心使用 intdiv() 或 (int)($gap / 2)，整除更安全
完整可运行的 PHP 8.1 示例代码
以下代码包含详细注释，支持整数数组，已在 PHP 8.1+ 环境验证通过：
<?php
function shellSort(array $arr): array
{
$n = count($arr);
if ($n <= 1) {
return $arr;
}
<pre class="brush:php;toolbar:false;">// 初始间隔：向下取整 n/2
$gap = intdiv($n, 2);
// 主循环：gap 递减至 1
while ($gap > 0) {
// 对每个子序列（从 gap 开始）执行插入排序
for ($i = $gap; $i < $n; $i++) {
$temp = $arr[$i];
$j = $i;
// 在子序列中向前比较：j-gap, j-2gap...
while ($j >= $gap && $arr[$j - $gap] > $temp) {
$arr[$j] = $arr[$j - $gap];
$j -= $gap;
}
$arr[$j] = $temp;
}
// 缩小间隔（经典 Knuth 序列也可用：gap = (gap * 3) + 1 → 倒序用）
$gap = intdiv($gap, 2);
}
return $arr;}
// 测试用例
$test = [64, 34, 25, 12, 22, 11, 90, 5];
echo "原始数组: " . implode(', ', $test) . "\n";
$sorted = shellSort($test);
echo "排序后: " . implode(', ', $sorted) . "\n";
// 输出：原始数组: 64, 34, 25, 12, 22, 11, 90, 5
// 排序后: 5, 11, 12, 22, 25, 34, 64, 90
?>
常见变体与优化建议（PHP 8.1 友好）
实际项目中可按需调整 gap 序列提升性能：
立即学习“PHP免费学习笔记（深入）”；
- Knuth 序列：gap = (gap * 3) + 1，生成如 1, 4, 13, 40…；升序生成后倒序使用，平均性能更优
- 使用生成器处理大数组：若内存敏感，可改写为 yield 版本（但希尔排序本身需随机访问，流式受限）
- 类型声明强化：PHP 8.1 支持联合类型，可写 function shellSort(array $arr): array，无需额外校验
- 避免全局变量依赖：函数保持纯函数特性，不修改原数组，符合现代 PHP 实践
时间复杂度与适用场景说明
希尔排序不是稳定排序（相同值的相对位置可能改变），但比普通插入排序快得多：
- 最坏情况：O(n²)，取决于 gap 序列（如全用 n/2 → n/4 → …，最坏仍接近 O(n²)）
- 平均情况：O(n^1.3) ~ O(n^1.5)，Knuth 序列下表现更佳
- 适用场景：中小规模数据、嵌入式或教学演示；不推荐替代 PHP 内置 sort() 处理万级+数组
