希尔排序(Shell Sort)是一种基于插入排序的排序算法,通过将原始数据分割成若干子序列分别进行插入排序,从而使得整个序列基本有序,最后再对全体记录进行一次直接插入排序。
以下是用PHP实现希尔排序的代码示例:
<?php
function shellSort(&$arr) {
$n = count($arr);
// 初始步长为数组长度的一半
for ($gap = intval($n / 2); $gap > 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 = [12, 34, 54, 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] => 12
[1] => 34
[2] => 54
[3] => 2
[4] => 3
)
Sorted array:
Array
(
[0] => 2
[1] => 3
[2] => 12
[3] => 34
[4] => 54
)
这个实现展示了如何使用PHP编写希尔排序算法,并对其进行了简单的测试。你可以根据需要调整和扩展此代码。