堆排序基本介紹

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

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

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

4、大頂堆舉例說明

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

5、小頂堆舉例說明

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

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

堆排序基本思想

1、將待排序序列構造成一個大頂堆

2、此時，整個序列的最大值就是堆頂的根節(jié)點。

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

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

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

堆排序圖解

步驟一

構造初始堆。將給定無序序列構造成一個大頂堆

1、假設給定無序序列結構如下

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

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

4、這時，交換導致了子根[4,5,6]結構混亂，繼續(xù)調整，[4,5,6]中6最大，交換4和6。

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

步驟二

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

1、將堆頂元素9和末尾元素4進行交換

2、重新調整結構，使其繼續(xù)滿足堆定義

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

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

代碼實現

      public static void headSort(int[] arr){
        //構建初始堆，將給定無序序列構造成一個大頂堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjust(arr,i,arr.length);
        }
        //將堆頂元素與末尾元素進行交換，使末尾元素最大，然后繼續(xù)調整堆
        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 待排序數組
     * @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;
    }

總結

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

最新評論