[[389058]]

 堆排序基本介紹

1. 堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最好、最壞、平均時間復雜度均為O(nlogn)，它是不穩定排序。
2. 堆是具有以下性質的完全二叉樹：每個節點的值都大于等于其左右子節點的值，稱為大頂堆，注意：沒有要求最有子節點值得大小關系。
3. 每個節點的值都小于等于左右子節點的值，稱為小頂堆。
4. 大頂堆的特點：arr[i ] >= arr[2i+1] && arr[i] >= arr[2i+2], i 對應第幾個節點，i 從編號0開始。
5. 小頂堆的特點: arr[i ] <= arr[2i+1] && arr[i] <= arr[2i+2], i 對應第幾個節點，i 從編號0開始。
6. 一般升序采用大頂堆，降序采用小頂堆。

堆排序基本思想

1. 將待排序序列構造成一個大頂堆
2. 此時，整個序列的最大值就是堆頂的根節點。
3. 將其與數組末尾元素進行交換，此時末尾就為最大值。
4. 然后將剩余 n-1 個元素重新構建成一個堆，這樣會得到n個元素的次小值。如此反復執行，便能得到一個有序序列。

可以看到在構建大頂堆的過程中，元素的個數逐漸減少，最后得到一個有序序列了

一個數組中非葉子節點的個數 = arr.length / 2 - 1

代碼案例

package com.xie.tree; 
 
public class HeapSort { 
    public static void main(String[] args) { 
        int[] arr = new int[8000000]; 
        for (int i = 0; i < 8000000; i++) { 
            arr[i] = (int) (Math.random() * 800000000); 
        } 
        long start = System.currentTimeMillis(); 
        heapSort(arr); 
        long end = System.currentTimeMillis(); 
        System.out.println("耗時：" + (end - start) + "ms"); 
        /** 
         * 800萬數據 
         * 堆排序!! 
         * 耗時：2482ms 
         */ 
    } 
 
    public static void heapSort(int[] arr) { 
        int temp = 0; 
        System.out.println("堆排序!!"); 
 
        //1.將無序序列構成一個堆，根據升序降序需求選擇大頂堆或小頂堆 
        for (int i = arr.length / 2 - 1; i >= 0; i--) { 
            adjustHeap(arr, i, arr.length); 
        } 
        //2.將堆頂元素與數組末尾元素交換，將最大元素"沉"到數組末端 
        //3.重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。 
        for (int j = arr.length - 1; j > 0; j--) { 
            //交換 
            temp = arr[j]; 
            arr[j] = arr[0]; 
            arr[0] = temp; 
            adjustHeap(arr, 0, j); 
        } 
    } 
 
    /** 
     * 將一個數組（二叉樹），調整成一個大頂堆 
     * 功能：完成將以 i 對應的非葉子節點的樹調整成大頂堆 
     * 
     * @param arr    待調整的數組 
     * @param i      表示非葉子節點在數組的索引 
     * @param length 表示對多少個元素進行調整,length在逐漸減少 
     */ 
    public static void adjustHeap(int[] arr, int i, int length) { 
        //先取出當前元素的值，保存在臨時變量 
        int temp = arr[i]; 
        //k = 2 * i + 1  是i節點的左子節點 
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) { 
            //當左子節點值小于右子節點值 
            if (k + 1 < length && arr[k] < arr[k + 1]) { 
                k++;//k指向右子節點 
            } 
 
            //如果子節點值大于父節點值 
            if (arr[k] > temp) { 
                //把較大的值賦給當前節點 
                arr[i] = arr[k]; 
                //!!! i指向k 繼續循環比較 
                i = k; 
            } else { 
                break; 
            } 
        } 
 
        //當for循環結束后，我們已經將以 i 為父節點的樹的最大值，放在了最頂。 
 
        //將temp值放到調整后的位置 
        arr[i] = temp; 
    } 
} 

 【編輯推薦】