学习PHP中堆排序算法的原理及时间复杂度分析
堆排序是一种基于堆数据结构的排序算法,它的时间复杂度为O(nlogn)。本文将介绍PHP语言中堆排序算法的原理,同时提供代码示例。
一、堆的定义和性质
在学习堆排序之前,首先需要了解堆的定义和性质。堆是一种完全二叉树,其每一个节点的值都大于或等于其子节点的值,我们把这样的堆称之为大顶堆。相反,如果每一个节点的值都小于或等于其子节点的值,我们称之为小顶堆。
由于堆的特性,堆顶元素即为最大或最小值,因此在堆排序中,我们通常将待排序的数组看作一个完全二叉树,并利用堆的特性进行排序。
二、堆排序算法的原理
堆排序算法主要分为构建堆和调整堆两个步骤。
- 构建堆(buildHeap):将待排序的数组调整为一个大顶堆。
步骤如下:
- 从最后一个非叶子节点(即n/2-1)开始逐个向前遍历,调用调整堆的函数(adjustHeap)。
- 调整堆的函数采用自上而下的方式,对当前节点及其子树进行调整,保证当前节点大于其子节点。
- 重复以上两个步骤,直到整个数组调整为一个大顶堆。
- 调整堆(adjustHeap):将当前节点及其子树调整为一个大顶堆。
步骤如下:
- 根据当前节点的位置计算其左右子节点的位置。
- 比较当前节点和其左右子节点的值,找到最大节点的位置。
- 如果最大节点的位置不是当前节点的位置,则交换最大节点和当前节点的值,并递归调用自身对交换后的子树进行调整。
- 排序(sortHeap):将堆顶元素(即数组的第一个元素)与最后一个叶子节点交换,然后对剩余的n-1个元素进行堆调整。
步骤如下:
- 将堆顶元素与最后一个叶子节点交换。
- 缩小堆的范围,即忽略已经排序好的最后一个叶子节点。
- 对缩小范围的堆进行调整,保持大顶堆的性质。
- 重复以上三个步骤,直到堆的范围缩小为1。
三、PHP代码示例
下面是PHP语言实现堆排序算法的示例代码:
function heapSort(&$arr) {
$length = count($arr);
// 构建大顶堆
for ($i = floor($length/2 - 1); $i >= 0; $i--) {
adjustHeap($arr, $i, $length);
}
// 调整堆并排序
for ($i = $length - 1; $i >= 0; $i--) {
// 交换堆顶元素和最后一个叶子节点
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
// 调整堆使其保持大顶堆性质
adjustHeap($arr, 0, $i);
}
}
function adjustHeap(&$arr, $i, $length) {
$largest = $i; // 最大值的位置
$left = $i * 2 + 1; // 左子节点的位置
$right = $i * 2 + 2; // 右子节点的位置
// 比较当前节点与左右子节点的值,找到最大值的位置
if ($left < $length && $arr[$left] > $arr[$largest]) {
$largest = $left;
}
if ($right < $length && $arr[$right] > $arr[$largest]) {
$largest = $right;
}
// 如果最大值的位置不是当前节点的位置,则交换两个位置的值,并递归调整堆
if ($largest != $i) {
$temp = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $temp;
adjustHeap($arr, $largest, $length);
}
}
// 测试
$arr = [8, 3, 6, 2, 9, 1];
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 6, 8, 9]
四、时间复杂度分析
堆排序的时间复杂度为O(nlogn)。其中,构建堆的时间复杂度为O(n),调整堆的时间复杂度为O(logn)。由于要对n个元素进行排序,因此总的时间复杂度为O(nlogn)。
总结
本文详细介绍了PHP语言中堆排序算法的原理,同时提供了相应的代码示例。堆排序是一种高效的排序算法,适用于待排序的数组较大的情况。通过学习堆排序算法,可以进一步提升对数据结构和算法的理解和应用能力。