希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过将原始数据分割成若干子序列分别进行插入排序,从而使得整个序列基本有序,最后再对全体记录进行一次直接插入排序。
以下是用PHP实现希尔排序的代码示例:
0; $gap = intval($gap / 2)) {
// 从第gap个元素开始,逐个对其所在的组进行直接插入排序
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;
}
}
}
// 测试代码
$array = [, , , 2, 3];
echo "Original array:\n";
print_r($array);
shellSort($array);
echo "Sorted array:\n";
print_r($array);
?>
代码解释:
- 初始化步长:$gap 初始值为数组长度的一半,每次循环后减半,直到 $gap 为 0。
- 分组插入排序:对于每个 $gap,从 $gap 位置开始,逐个对其所在的组进行直接插入排序。
- 插入排序逻辑:在插入排序中,如果当前元素小于前一个元素(间隔为 $gap),则交换它们的位置,继续向前比较,直到找到合适的位置。
运行结果:
Original array:
Array
(
[0] =>
[1] =>
[2] =>
[3] => 2
[4] => 3
)
Sorted array:
Array
(
[0] => 2
[1] => 3
[2] =>
[3] =>
[4] =>
)
这个实现展示了如何使用PHP编写希尔排序算法,并对其进行了简单的测试。你可以根据需要调整和扩展此代码。