堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。堆分为大根堆和小根堆。大根堆的要求是每个节点的值都不大于其父节点的值。 在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。查看完整代码
1.堆的存储：ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n/2），当然，这是小根堆，大根堆则换成>=号。//k(i）父节点，K(2i）则是左子节点，k(2i+1）是右子节点
2.算法思想：
(1) 先将构建一个大根堆，此堆为初始的无序区
(2) 再将堆顶(根节点)与最后一个元素交换，由此得到新的无序区array[1..n-1]和有序区array[n]。
(3)由于交换后新的无序区可能违反堆性质，故应将新的无序区再一次调整为堆。然后再进行(2)操作，直到无序区只有一个元素为止。此时排序结束
3.算法步骤：
(1)建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。
(2)调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
(3)堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)
4.算法分析：
时间复杂度：O(N*logN)由于建初始堆所需的比较次数较多，所以堆排序不适合较少的
空间复杂度：堆排序是就地排序，空间复杂度O(1）
稳定性：不稳定的一种排序算法
网友评论