快捷導(dǎo)航

Java實(shí)現(xiàn)堆排序和圖解

更新時(shí)間：2021年07月09日 08:49:35 作者：程序dunk

如果將堆理解為二叉樹(shù),那么樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字,堆排序的時(shí)間復(fù)雜度為O(N*logN),這里我們就來(lái)詳解堆排序算法原理及Java版的代碼實(shí)現(xiàn)

堆排序基本介紹

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

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

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

4、大頂堆舉例說(shuō)明

大頂堆特點(diǎn)：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2] // i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i從0開(kāi)始編號(hào)

5、小頂堆舉例說(shuō)明

小頂堆：arr[i] <= arr[2*i+1] && arr[i] <= arr[2*i+2] // i 對(duì)應(yīng)第幾個(gè)節(jié)點(diǎn)，i從0開(kāi)始編號(hào)

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

堆排序基本思想

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

2、此時(shí)，整個(gè)序列的最大值就是堆頂?shù)母?jié)點(diǎn)。

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

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

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

堆排序圖解

步驟一

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

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

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

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

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

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

步驟二

將堆頂元素與末尾元素進(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ù)過(guò)程，繼續(xù)進(jìn)行調(diào)整，交換，如此反復(fù)進(jìn)行，最終使得整個(gè)序列有序

代碼實(shí)現(xiàn)

      public static void headSort(int[] arr){
        //構(gòu)建初始堆，將給定無(wú)序序列構(gòu)造成一個(gè)大頂堆
        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 最后一個(gè)非葉子節(jié)點(diǎn)
     * @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;
    }