一、定義

堆排序（Heap Sort）是一種基于優(yōu)先隊列（堆實現(xiàn)）的排序方式。
堆排序的步驟如下：

1. 初始時待排序元素保存在數(shù)組形式的二叉樹中：

   
   

2. 排序時，從樹的最右子結(jié)點的父結(jié)點（上圖的5-E）開始下沉，以提高性能，直到根結(jié)點為止：

for (int k = n/2; k >= 1; k--)
    sink(pq, k, n);

此時根結(jié)點就是最大元素（假設(shè)大頂堆）

3. 接著重復以下循環(huán)：
   將根結(jié)點與最右下子結(jié)點交換，然后再對根結(jié)點下沉，共進行N次。

   
   

二、實現(xià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)