[[389058]]

 堆排序基本介紹

1. 堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計(jì)的一種排序算法，堆排序是一種選擇排序，它的最好、最壞、平均時(shí)間復(fù)雜度均為O(nlogn)，它是不穩(wěn)定排序。
2. 堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于等于其左右子節(jié)點(diǎn)的值，稱(chēng)為大頂堆，注意：沒(méi)有要求最有子節(jié)點(diǎn)值得大小關(guān)系。
3. 每個(gè)節(jié)點(diǎn)的值都小于等于左右子節(jié)點(diǎn)的值，稱(chēng)為小頂堆。
4. 大頂堆的特點(diǎn)：arr[i ] >= arr[2i+1] && arr[i] >= arr[2i+2], i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i 從編號(hào)0開(kāi)始。
5. 小頂堆的特點(diǎn): arr[i ] <= arr[2i+1] && arr[i] <= arr[2i+2], i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i 從編號(hào)0開(kāi)始。
6. 一般升序采用大頂堆，降序采用小頂堆。

堆排序基本思想

1. 將待排序序列構(gòu)造成一個(gè)大頂堆
2. 此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。
3. 將其與數(shù)組末尾元素進(jìn)行交換，此時(shí)末尾就為最大值。
4. 然后將剩余 n-1 個(gè)元素重新構(gòu)建成一個(gè)堆，這樣會(huì)得到n個(gè)元素的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列。

可以看到在構(gòu)建大頂堆的過(guò)程中，元素的個(gè)數(shù)逐漸減少，最后得到一個(gè)有序序列了

一個(gè)數(shù)組中非葉子節(jié)點(diǎn)的個(gè)數(shù) = 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("耗時(shí)：" + (end - start) + "ms"); 
        /** 
         * 800萬(wàn)數(shù)據(jù) 
         * 堆排序!! 
         * 耗時(shí)：2482ms 
         */ 
    } 
 
    public static void heapSort(int[] arr) { 
        int temp = 0; 
        System.out.println("堆排序!!"); 
 
        //1.將無(wú)序序列構(gòu)成一個(gè)堆，根據(jù)升序降序需求選擇大頂堆或小頂堆 
        for (int i = arr.length / 2 - 1; i >= 0; i--) { 
            adjustHeap(arr, i, arr.length); 
        } 
        //2.將堆頂元素與數(shù)組末尾元素交換，將最大元素"沉"到數(shù)組末端 
        //3.重新調(diào)整結(jié)構(gòu)，使其滿(mǎn)足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個(gè)序列有序。 
        for (int j = arr.length - 1; j > 0; j--) { 
            //交換 
            temp = arr[j]; 
            arr[j] = arr[0]; 
            arr[0] = temp; 
            adjustHeap(arr, 0, j); 
        } 
    } 
 
    /** 
     * 將一個(gè)數(shù)組（二叉樹(shù)），調(diào)整成一個(gè)大頂堆 
     * 功能：完成將以 i 對(duì)應(yīng)的非葉子節(jié)點(diǎn)的樹(shù)調(diào)整成大頂堆 
     * 
     * @param arr    待調(diào)整的數(shù)組 
     * @param i      表示非葉子節(jié)點(diǎn)在數(shù)組的索引 
     * @param length 表示對(duì)多少個(gè)元素進(jìn)行調(diào)整,length在逐漸減少 
     */ 
    public static void adjustHeap(int[] arr, int i, int length) { 
        //先取出當(dāng)前元素的值，保存在臨時(shí)變量 
        int temp = arr[i]; 
        //k = 2 * i + 1  是i節(jié)點(diǎn)的左子節(jié)點(diǎn) 
        for (int k = 2 * i + 1; k < length; k = k * 2 + 1) { 
            //當(dāng)左子節(jié)點(diǎn)值小于右子節(jié)點(diǎn)值 
            if (k + 1 < length && arr[k] < arr[k + 1]) { 
                k++;//k指向右子節(jié)點(diǎn) 
            } 
 
            //如果子節(jié)點(diǎn)值大于父節(jié)點(diǎn)值 
            if (arr[k] > temp) { 
                //把較大的值賦給當(dāng)前節(jié)點(diǎn) 
                arr[i] = arr[k]; 
                //!!! i指向k 繼續(xù)循環(huán)比較 
                i = k; 
            } else { 
                break; 
            } 
        } 
 
        //當(dāng)for循環(huán)結(jié)束后，我們已經(jīng)將以 i 為父節(jié)點(diǎn)的樹(shù)的最大值，放在了最頂。 
 
        //將temp值放到調(diào)整后的位置 
        arr[i] = temp; 
    } 
} 

 【編輯推薦】