四时宝库

程序员的知识宝库

php实现希尔排序

希尔排序(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);
?>

代码解释:

  1. 初始化步长$gap 初始值为数组长度的一半,每次循环后减半,直到 $gap 为 0。
  2. 分组插入排序:对于每个 $gap,从 $gap 位置开始,逐个对其所在的组进行直接插入排序。
  3. 插入排序逻辑:在插入排序中,如果当前元素小于前一个元素(间隔为 $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编写希尔排序算法,并对其进行了简单的测试。你可以根据需要调整和扩展此代码。

发表评论:

控制面板
您好,欢迎到访网站!
  查看权限
网站分类
最新留言
    友情链接