排序算法 - 7堆排序 - 《数据结构/算法》

算法步骤
效率分析
算法稳定性

https://www.yduba.com/biancheng-4622548289.html
堆是一种特殊的完全二叉树
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

算法步骤

创建一个堆 H[0…n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1；

效率分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
平均性能：O(n * logn)
其他性能：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

算法稳定性
我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。

动图演示

代码实现 ```php <?php function swap(&$x, &$y) { $t = $x; $x = $y; $y = $t; }

function max_heapify(&$arr, $start, $end) { // 建立父节点指标和子节点指标 $dad = $start; $son = $dad * 2 + 1; if ($son >= $end) //若子节点指标超过范围直接跳出函数 return;

// 先比较两个子节点大小，选择最大的
if ($son + 1 < $end && $arr[$son] < $arr[$son + 1])
    $son++;
// 如果父节点小于子节点时，交换父子内容再继续子节点和孙节点比较
if ($arr[$dad] <= $arr[$son]) 
{
    swap($arr[$dad], $arr[$son]);
    max_heapify($arr, $son, $end);
}

}

function heap_sort($arr) { $len = count($arr);

//初始化，i从最后一个父节点开始调整
for ($i = $len / 2 - 1; $i >= 0; $i--)
    max_heapify($arr, $i, $len);

//先将第一个元素和已排好元素前一位做交换，再从新调整，直到排序完毕
for ($i = $len - 1; $i > 0; $i--) 
{
    swap($arr[0], $arr[$i]);
    max_heapify($arr, 0, $i);
}
return $arr;

} ```

7堆排序

算法步骤

效率分析

算法稳定性