一、定义
堆排序（Heap Sort）是一种基于优先队列（堆实现）的排序方式。
堆排序的步骤如下：
-
初始时待排序元素保存在数组形式的二叉树中：
排序时，从树的最右子结点的父结点（上图的5-E）开始下沉，以提高性能，直到根结点为止：
for (int k = n/2; k >= 1; k--)
sink(pq, k, n);
此时根结点就是最大元素（假设大顶堆）
-
接着重复以下循环：
将根结点与最右下子结点交换，然后再对根结点下沉，共进行N次。
二、实现
public class HeapSort {
// This class should not be instantiated.
private HeapSort() { }
public static void sort(Comparable[] pq) {
int n = pq.length;
for (int k = n/2; k >= 1; k--)
sink(pq, k, n);
while (n > 1) {
exch(pq, 1, n--);
sink(pq, 1, n);
}
}
/***************************************************************************
* Helper functions to restore the heap invariant.
***************************************************************************/
private static void sink(Comparable[] pq, int k, int n) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(pq, j, j+1)) j++;
if (!less(pq, k, j)) break;
exch(pq, k, j);
k = j;
}
}
/***************************************************************************
* Helper functions for comparisons and swaps.
* Indices are "off-by-one" to support 1-based indexing.
***************************************************************************/
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i-1].compareTo(pq[j-1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i-1];
pq[i-1] = pq[j-1];
pq[j-1] = swap;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
}
三、性能分析
- 时间复杂度
O(NlgN) - 空间复杂度
O(N)
