php堆排序

php堆排序，堆排序是一种比冒泡排序更好的排序方法。

虽然复杂了一些，但是在处理长数据数组时更有性价比。

<?php
function swp(&$arr, $n, $i) {
    $root = $i;       // 初始化最大值为根节点
    $left = 2 * $i + 1;  // 左子节点
    $right = 2 * $i + 2; // 右子节点

    // 如果左子节点存在且大于根节点
    if ($left < $n && $arr[$left] > $arr[$root]) {
        $root = $left;
    }

    // 如果右子节点存在且大于根节点
    if ($right < $n && $arr[$right] > $arr[$root]) {
        $root = $right;
    }

    // 如果最大值不是根节点
    if ($root != $i) {
        // 交换根节点和最大值节点
        list($arr[$i], $arr[$root]) = array($arr[$root], $arr[$i]);
        // 递归调整子树
        swp($arr, $n, $root);
    }
}

function heapSort(&$arr) {
    $n = count($arr);

    // 构建最大堆（从最后一个非叶子节点开始）
    for ($i = intval($n / 2) - 1; $i >= 0; $i--) {
        swp($arr, $n, $i);
    }

    // 逐个提取堆顶元素
    for ($i = $n - 1; $i > 0; $i--) {
        // 将堆顶元素（最大值）与末尾元素交换
        list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);
        // 调整剩余堆
        swp($arr, $i, 0);
    }
}

// 示例
$arr = [4, 10, 3, 5, 1];
echo "排序前: " . implode(", ", $arr) . "\n";

heapSort($arr);

echo "排序后: " . implode(", ", $arr) . "\n";
?>