php 实现堆排序

堆排序的基本概念

堆排序是一种基于二叉堆数据结构的比较排序算法。二叉堆是一种完全二叉树，可以分为最大堆和最小堆。在最大堆中，父节点的值总是大于或等于子节点的值；在最小堆中，父节点的值总是小于或等于子节点的值。

实现堆排序的步骤

构建最大堆：将无序数组构建成一个最大堆，此时堆顶元素为最大值。 交换堆顶与末尾元素：将堆顶元素与末尾元素交换，缩小堆的范围（排除已排序的部分）。 调整堆结构：对剩余的堆进行调整，使其重新满足最大堆的性质。 重复上述步骤，直到堆的大小为1。

PHP实现堆排序代码

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

    // 构建最大堆
    for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 交换堆顶与末尾元素，并调整堆
    for ($i = $n - 1; $i > 0; $i--) {
        // 交换堆顶和当前末尾元素
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整堆
        heapify($arr, $i, 0);
    }
}

function heapify(&$arr, $n, $i) {
    $largest = $i;      // 初始化最大值为当前节点
    $left = 2 * $i + 1; // 左子节点
    $right = 2 * $i + 2; // 右子节点

    // 如果左子节点大于当前最大值
    if ($left < $n && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }

    // 如果右子节点大于当前最大值
    if ($right < $n && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值不是当前节点，交换并继续调整
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        heapify($arr, $n, $largest);
    }
}

// 测试代码
$array = [12, 11, 13, 5, 6, 7];
heapSort($array);
print_r($array);

代码说明

heapSort函数是堆排序的主函数，负责构建最大堆和交换堆顶元素。heapify函数用于调整堆结构，确保父节点的值大于子节点的值。

构建最大堆时，从最后一个非叶子节点开始调整，逐步向上。交换堆顶元素后，重新调整堆结构，直到所有元素有序。

时间复杂度分析

堆排序的时间复杂度为O(n log n)，其中构建堆的时间为O(n)，每次调整堆的时间为O(log n)。堆排序是一种原地排序算法，空间复杂度为O(1)。