堆排序基本介紹

1、堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。

2、堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆, 注意 : 沒有要求結(jié)點的左孩子的值和右孩子的值的大小關(guān)系。

3、每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆

4、大頂堆舉例說明

大頂堆特點：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 對應(yīng)第幾個節(jié)點，i從0開始編號

5、小頂堆舉例說明

小頂堆：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 對應(yīng)第幾個節(jié)點，i從0開始編號

6、一般升序采用大頂堆，降序采用小頂堆

堆排序基本思想

1、將待排序序列構(gòu)造成一個大頂堆

2、此時，整個序列的最大值就是堆頂?shù)母?jié)點。

3、將其與末尾元素進(jìn)行交換，此時末尾就為最大值。

4、然后將剩余n-1個元素重新構(gòu)造成一個堆，這樣會得到n個元素的次小值。如此反復(fù)執(zhí)行，便能得到一個有序序列了。

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

堆排序圖解

步驟一

構(gòu)造初始堆。將給定無序序列構(gòu)造成一個大頂堆

1、假設(shè)給定無序序列結(jié)構(gòu)如下

2、此時我們從最后一個非葉子結(jié)點開始（葉結(jié)點自然不用調(diào)整，第一個非葉子結(jié)點 arr.length/2-1=5/2-1=1，也就是下面的6結(jié)點），從左至右，從下至上進(jìn)行調(diào)整。

3、找到第二個非葉節(jié)點4，由于[4,9,8]中9元素最大，4和9交換

4、這時，交換導(dǎo)致了子根[4,5,6]結(jié)構(gòu)混亂，繼續(xù)調(diào)整，[4,5,6]中6最大，交換4和6。

此時，我們就將一個無序序列構(gòu)造成了一個大頂堆。

步驟二

將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大。然后繼續(xù)調(diào)整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反復(fù)進(jìn)行交換、重建、交換。

1、將堆頂元素9和末尾元素4進(jìn)行交換

2、重新調(diào)整結(jié)構(gòu)，使其繼續(xù)滿足堆定義

3、再將堆頂元素8與末尾元素5進(jìn)行交換，得到第二大元素8.

4、后續(xù)過程，繼續(xù)進(jìn)行調(diào)整，交換，如此反復(fù)進(jìn)行，最終使得整個序列有序

代碼實現(xiàn)

      public static void headSort(int[] arr){
        //構(gòu)建初始堆，將給定無序序列構(gòu)造成一個大頂堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjust(arr,i,arr.length);
        }
        //將堆頂元素與末尾元素進(jìn)行交換，使末尾元素最大，然后繼續(xù)調(diào)整堆
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            adjust(arr,0,i);
        }
    }
    /**
     *
     * @param arr 待排序數(shù)組
     * @param i 最后一個非葉子節(jié)點
     * @param length
     */
    public static void adjust(int[] arr,int i,int length){
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            if((k + 1) < length && arr[k] < arr[k + 1])
                k++;
            if(arr[k] > temp){
                arr[i] = arr[k];
                i = k;
            }else
                break;
        }
        arr[i] = temp;
    }

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論