【排序知多少】堆排序详解

堆排序的概述 堆是具有下列特性的完全二叉树:每个节点的值都大于或等于其左右孩子的节点的值,成为大顶堆,或者每个节点的值都小于或等于其左右孩子节点的值,成为小顶堆。 在选择到最小记录同时,并根据比较结果对其他记录做出相应调整。这样的排序整体效率非常高。 堆排序的思路 堆排序(Heap Sort)就是利用堆进行排序的方法。他的基本思想是,将待排序的序列构造成一个大顶堆,此时,整个序列的最大值就是对定的根节点。将他移走(其实就是将其余对数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构成一个堆,这样就会得到n个元素中的次小值。如此反复,便能得到一个有序序列。 堆排序的复杂度