堆排序是利用二叉堆的自调整特性将数组变为有序序列的排序方法
二叉堆的特性：
- 最大堆的堆顶是整个堆中的最大元素。
- 最小堆的堆顶是整个堆中的最小元素。
堆排序算法的步骤：
- 把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
- 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。
具体代码如下：
此代码二叉堆的构建有些问题，输出的并不是一个最大堆，有时间再思考下，先将代码贴出
class Code{
/**
* “下沉”调整 自上而下比较父节点和子节点
* @param array 待调整的堆
* @param parentIndex 要“下沉”的父节点
* @param length 堆的有效大小
*/
function downAdjust(&$arr,$parentIndex,$length){
// tmp 保存父节点值，用于最后的赋值
$tmp = $arr[$parentIndex];
$childIndex = $parentIndex*2 + 1;
while ($childIndex < $length) {
// 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
if($childIndex+1 < $length && $arr[$childIndex] < $arr[$childIndex+1]){
$childIndex++;
}
// 如果父节点大于任何一个孩子的值，则直接跳出
if($tmp >= $arr[$childIndex]){
break;
}
//无须真正交换，单向赋值即可
$arr[$parentIndex] = $arr[$childIndex];
//下移父节点和子节点，继续对比调整
$parentIndex = $childIndex;
$childIndex = $parentIndex*2 + 1;
}
$arr[$parentIndex] = $tmp;
}
/**
* 堆排序（升序）
* @param arr 待调整的堆
*/
function heapSort(&$arr){
$intLength = count($arr);
//1.把无序数组构建为最大堆
for ($i=($intLength-2)/2; $i >= 0; $i--) {
$this->downAdjust($arr,$i,$intLength);
}
//2.循环删除堆顶，移动到堆的尾部，调整堆产生新的堆顶
for ($i=$intLength-1; $i > 0; $i--) {
//最后一个元素与第一个元素交换位置
$tmp = $arr[$i];
$arr[$i] = $arr[0];
$arr[0] = $tmp;
//下沉调整最大堆
$this->downAdjust($arr,0,$i);
}
}
//运行
function run(){
$arr = array(8,5,7,4,2,0,1,3,9);
$this->heapSort($arr);
print_r($arr);
}
}
$obj = new Code();
$obj->run();
空间复杂度是O(1)，因为并没有开辟额外的集合空间
时间复杂度的计算
堆排序算法的步骤。
- 把无序数组构建成二叉堆。
- 循环删除堆顶元素，并将该元素移到集合尾部，调整堆产生新的堆顶。
第1步，把无序数组构建成二叉堆，这一步的时间复杂度是O(n)。
第2步，需要进行n-1次循环。每次循环调用一次downAdjust方法，所以第2步的计算规模是 (n-1)×logn ，时间复杂度为O(nlogn)。
