分類 -------------- 內(nèi)部比較排序
數(shù)據(jù)結(jié)構(gòu) ---------- 數(shù)組
最差時間復(fù)雜度 ---- O(nlogn)
最優(yōu)時間復(fù)雜度 ---- O(nlogn)
平均時間復(fù)雜度 ---- O(nlogn)
所需輔助空間 ------ O(1)
穩(wěn)定性 ------------ 不穩(wěn)定

原理

???????堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)（通常堆是通過一維數(shù)組來實現(xiàn)的），并同時滿足堆的性質(zhì)：即子結(jié)點的鍵值總是小于（或者大于）它的父節(jié)點。

步驟

1. 創(chuàng)建一個堆
2. 把堆頂元素(最大值)和堆尾元素互換
3. 把堆的尺寸縮小1，并調(diào)用heapify(A, 0)從新的堆頂元素開始進行堆調(diào)整
4. 重復(fù)步驟2，直到堆的尺寸為1

代碼實現(xiàn)

public class HeapSort {

    // 堆大小
    private int heapsize;

    // 堆調(diào)整函數(shù)(這里使用的是最大堆)
    private void heapify(Integer a[], int i)
    {
        // 左孩子索引
        int leftchild = 2 * i + 1;
        // 右孩子索引
        int rightchild = 2 * i + 2;
        // 選出當(dāng)前結(jié)點與左右孩子之中的最大值
        int largest;

        if (leftchild < heapsize && a[leftchild] > a[i]){
            largest = leftchild;
        }
        else{
            largest = i;
        }

        if (rightchild < heapsize && a[rightchild] > a[largest]) {
            largest = rightchild;
        }

        if (largest != i)
        {
            // 把當(dāng)前結(jié)點和它的最大(直接)子節(jié)點進行交換
            Tool.exchange(a, i, largest);
            // 遞歸調(diào)用，繼續(xù)從當(dāng)前結(jié)點向下進行堆調(diào)整
            heapify(a, largest);
        }
    }

    // 建堆函數(shù)
    private void buildheap(Integer a[], int n)
    {
        heapsize = n;
        // 對每一個非葉結(jié)點
        for (int i = heapsize / 2 - 1; i >= 0; i--) {
            // 不斷的堆調(diào)整
            heapify(a, i);
        }
    }

    public void heapsort(Integer a[], int n)
    {
        buildheap(a, n);
        for (int i = n - 1; i >= 1; i--)
        {
            // 將堆頂元素(當(dāng)前最大值)與堆的最后一個元素互換(該操作很有可能把后面元素的穩(wěn)定性打亂,所以堆排序是不穩(wěn)定的排序算法)
            Tool.exchange(a, 0, i);
            // 從堆中去掉最后一個元素
            heapsize--;
            // 從新的堆頂元素開始進行堆調(diào)整
            heapify(a, 0);
        }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        HeapSort sort = new HeapSort();
        sort.heapsort(a,a.length);
        System.out.println("array by HeapSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

實現(xiàn)結(jié)果

array by HeapSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]