php堆排序代码示例

涛哥
PHP代码

以下是 PHP 堆排序的示例代码，代码实现了以下需求：

实现一个 heapSort 函数，该函数可以对传入的数组进行堆排序。

heapSort 函数首先建立最大堆，然后将堆顶元素和堆底元素交换，并重新维护最大堆，直到所有元素都被排序。

heapify 函数用于维护最大堆。对于当前节点，我们先假设它是最大的，然后比较它和它的左右子节点的大小，如果有子节点比它更大，就交换它们的位置，并递归地对子节点进行堆维护。

swap 函数用于交换数组中的两个元素，用于堆排序过程中交换堆顶和堆底元素的位置。

最后，我们对一个示例数组进行堆排序，并输出结果。

需要注意的是，堆排序的时间复杂度为 O(nlogn)，具有较好的排序性能，适合用于大规模数据的排序。

以下是 PHP 堆排序的示例代码：

<?php
function heapSort(&$arr) {
    $len = count($arr);

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

    // 交换堆顶和堆底元素，并重新维护最大堆
    for ($i = $len - 1; $i >= 0; $i--) {
        swap($arr, 0, $i);
        heapify($arr, $i, 0);
    }
}

// 维护最大堆的过程
function heapify(&$arr, $len, $i) {
    $largest = $i; // 假设当前节点是最大的
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;

    if ($left < $len && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }

    if ($right < $len && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $len, $largest);
    }
}

// 交换数组中的两个元素
function swap(&$arr, $i, $j) {
    $tmp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $tmp;
}

// 示例
$arr = array(3, 7, 4, 8, 6, 2, 1, 5);
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 4, 5, 6, 7, 8]
?>

在这个php堆排序代码示例中，我们首先定义了一个 heapSort 函数，用于进行堆排序。堆排序分为两个过程，首先是建立最大堆，然后是将堆顶元素和堆底元素交换，并重新维护最大堆。

在 heapify 函数中，我们使用递归的方式维护最大堆。对于当前节点，我们先假设它是最大的，然后比较它和它的左右子节点的大小，如果有子节点比它更大，就交换它们的位置，并递归地对子节点进行堆维护。

最后，我们定义了一个 swap 函数用于交换数组中的两个元素。最后，我们对一个示例数组进行堆排序，并输出结果。

需要注意的是，由于 PHP 的数组下标是从 0 开始的，因此在堆排序的实现中需要对数组下标进行适当的计算。

猜你喜欢：java实现堆栈功能代码

 
  • 堆排序
  • 数组