排序算法之——堆排序分析

排序算法之——堆排序分析

前言

上一篇文章中对堆进行了分析，接下来趁热打铁，一起来学习一下堆排序算法。

思路

有点类似选择排序的思想，右侧都是已经排好序的，不停的从左侧选择最小者加入右侧。

假设输入序列：[59, 7, 19, 43, 77, 52, 91]

最后得到的的堆序列：[91, 77, 59, 43, 7, 52, 19]

执行删除操作，如下图所示，虚线代表节点已经不属于堆了。97放到最后的位置，

堆大小减1，现在该堆只包含6个元素。数组中蓝色边框表示右侧已经排好序的数列。

但此时还需要对19进行下滤操作，下滤完成后如图：

继续删除77，并进行下滤：

继续删除59，并进行下滤：

注意最后一个节点是7而不是52。

继续删除52，并下滤：

继续删除43，并下滤(数据量是不是太大了，还没画完。。。)：

上面是删除了19的结果，可以看到，此时堆中仅剩一个节点，但是已经不需要进行任何操作了，因为该节点必然是最小的。这一点可以在代码中体现出来。

代码

/** * 通过Max堆实现堆排序，堆排序的数组包含0处的位置 * @param array * @param */public static > void heapSort(E[] array) { //因为包含索引0处的位置，最后内部节点的计算也不一样 //首先是建堆 for (int i = array.length/2 - 1;i >= 0; i--) { percDown(array,i,array.length); } for (int i = array.length - 1; i > 0; i--) {//为啥不是i>=0? 因为当i为1时，此时堆中仅剩一个节点，但是已经不需要进行任何操作了 swap(array,0,i);//因为大顶堆中最大元素位置一定是堆顶，0的位置 ，每次交换堆顶和最后一个元素的位置 percDown(array,0,i);//所需处理的长度刚好也是i }}private static > void percDown(E[] array,int hole,int size) { int child; E tmp = array[hole]; while ((hole * 2 + 1) < size) { //如果有孩子，hole不停的往下 child = hole * 2 + 1; //若有右孩子，且右孩子更大 if (child != size -1 && array[child].compareTo(array[child + 1]) < 0) { child++;//取右孩子 } //如果tmp小于孩子节点的值 if (tmp.compareTo(array[child]) < 0) { //hole位置填充最大孩子节点的值 array[hole] = array[child]; hole = child;//继续比较 } else { break; } } array[hole] = tmp;}private static void swap(E[] array,int i,int j) { E tmp = array[i]; array[i] = array[j]; array[j] = tmp;}

注意，当数组下标从0开始时，计算：

左节点：​​i * 2 + 1​​右节点：​​i * 2 + 2​​有孩子：​​i * 2 + 1 < 堆大小​​有右孩子：​​i * 2 + 1 != 堆大小 - 1​​

复杂度和稳定性

时间复杂度

稳定性

堆排序是不稳定的算法。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。