JAVA十大排序算法之堆排序詳解

更新時(shí)間：2021年08月23日 10:44:31 作者：阿粵Ayue

這篇文章主要介紹了java中的冒泡排序，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考

堆排序

這里的堆并不是JVM中堆棧的堆，而是一種特殊的二叉樹(shù)，通常也叫作二叉堆。它具有以下特點(diǎn)：

它是完全二叉樹(shù)
堆中某個(gè)結(jié)點(diǎn)的值總是不大于或不小于其父結(jié)點(diǎn)的值

知識(shí)補(bǔ)充

二叉樹(shù)

樹(shù)中節(jié)點(diǎn)的子節(jié)點(diǎn)不超過(guò)2的有序樹(shù)

滿二叉樹(shù)

二叉樹(shù)中除了葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都為2，則此二叉樹(shù)為滿二叉樹(shù)。

完全二叉樹(shù)

如果對(duì)滿二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)，約定編號(hào)從根結(jié)點(diǎn)起，自上而下，自左而右。則深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹(shù)。

特點(diǎn)：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹(shù)的左部。需要注意的是，滿二叉樹(shù)肯定是完全二叉樹(shù)，而完全二叉樹(shù)不一定是滿二叉樹(shù)。

二叉堆

二叉堆是一種特殊的堆，可以被看做一棵完全二叉樹(shù)的數(shù)組對(duì)象，而根據(jù)其性質(zhì)又可以分為下面兩種：

大根堆：每一個(gè)根節(jié)點(diǎn)都大于等于它的左右孩子節(jié)點(diǎn)，也叫最大堆
小根堆：每一個(gè)根節(jié)點(diǎn)都小于等于它的左右孩子節(jié)點(diǎn)，也叫最小堆

如果把一個(gè)數(shù)組通過(guò)大根堆的方式來(lái)表示（數(shù)組元素的值是可變的），如下：

由此可以推出：

對(duì)于位置為 k 的節(jié)點(diǎn)，其子節(jié)點(diǎn)的位置分別為，左子節(jié)點(diǎn) = 2k + 1，右子節(jié)點(diǎn) = 2(k + 1)

如：對(duì)于 k = 1，其節(jié)點(diǎn)的對(duì)應(yīng)數(shù)組為 5

左子節(jié)點(diǎn)的位置為 3，對(duì)應(yīng)數(shù)組的值為 3

右子節(jié)點(diǎn)的位置為 4，對(duì)應(yīng)數(shù)組的值為 2

最后一個(gè)非葉子節(jié)點(diǎn)的位置為 (n/2) - 1，n為數(shù)組長(zhǎng)度

如：數(shù)組長(zhǎng)度為6，則 (6/2) - 1 = 2，即位置 2 為最后一個(gè)非葉子節(jié)點(diǎn)

給定一個(gè)隨機(jī)數(shù)組[35,63,48,9,86,24,53,11]，將該數(shù)組視為一個(gè)完全二叉樹(shù)：

從上圖很明顯的可以看出，這個(gè)二叉樹(shù)不符合大根堆的定義，但是可以通過(guò)調(diào)整，使它變?yōu)樽畲蠖?。如?strong>從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，從下到上，從右往左調(diào)整，則：

通過(guò)上面的調(diào)整，該二叉樹(shù)為最大堆，這個(gè)時(shí)候開(kāi)始排序，排序規(guī)則：

將堆頂元素和尾元素交換交換
后重新調(diào)整元素的位置，使之重新變成二叉堆

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

public class HeapSort {
    public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    public static int[] sort(int[] array) {
        //數(shù)組的長(zhǎng)度
        int length = array.length;
        if (length < 2) return array;
        //首先構(gòu)建一個(gè)最大堆
        buildMaxHeap(array);
        //調(diào)整為最大堆之后，頂元素為最大元素并與微元素交換
        while (length > 0) {//當(dāng)lenth <= 0時(shí)，說(shuō)明已經(jīng)到堆頂
            //交換
            swap(array, 0, length - 1);
            length--;//交換之后相當(dāng)于把樹(shù)中的最大值彈出去了，所以要--
            //交換之后從上往下調(diào)整使之成為最大堆
            adjustHeap(array, 0, length);
        }
        return array;
    }
    //對(duì)元素組構(gòu)建為一個(gè)對(duì)應(yīng)數(shù)組的最大堆
    private static void buildMaxHeap(int[] array) {
        //在之前的分析可知，最大堆的構(gòu)建是從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，從下往上，從右往左調(diào)整
        //最后一個(gè)非葉子節(jié)點(diǎn)的位置為：array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            //調(diào)整使之成為最大堆
            adjustHeap(array, i, array.length);
        }
    }
    /**
     * 調(diào)整
     * @param parent 最后一個(gè)非葉子節(jié)點(diǎn)
     * @param length 數(shù)組的長(zhǎng)度
     */
    private static void adjustHeap(int[] array, int parent, int length) {
        //定義最大值的索引
        int maxIndex = parent;
        //parent為對(duì)應(yīng)元素的位置（數(shù)組的索引）
        int left = 2 * parent + 1;//左子節(jié)點(diǎn)對(duì)應(yīng)元素的位置
        int right = 2 * (parent + 1);//右子節(jié)點(diǎn)對(duì)應(yīng)元素的位置
        //判斷是否有子節(jié)點(diǎn)，再比較父節(jié)點(diǎn)和左右子節(jié)點(diǎn)的大小
        //因?yàn)閜arent最后一個(gè)非葉子節(jié)點(diǎn)，所以如果有左右子節(jié)點(diǎn)則節(jié)點(diǎn)的位置都小于數(shù)組的長(zhǎng)度
        if (left < length && array[left] > array[maxIndex]) {//左子節(jié)點(diǎn)如果比父節(jié)點(diǎn)大
            maxIndex = left;
        }
        if (right < length && array[right] > array[maxIndex]) {//右子節(jié)點(diǎn)如果比父節(jié)點(diǎn)大
            maxIndex = right;
        }
        //maxIndex為父節(jié)點(diǎn)，若發(fā)生改變則說(shuō)明不是最大節(jié)點(diǎn)，需要交換
        if (maxIndex != parent) {
            swap(array, maxIndex, parent);
            //交換之后遞歸再次調(diào)整比較
            adjustHeap(array, maxIndex, length);
        }
    }
    //交換
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

時(shí)間復(fù)雜度

堆的時(shí)間復(fù)雜度是 O(nlogn)

參考：堆排序的時(shí)間復(fù)雜度分析

算法穩(wěn)定性

堆的結(jié)構(gòu)為，對(duì)于位置為 k 的節(jié)點(diǎn)，其子節(jié)點(diǎn)的位置分別為，左子節(jié)點(diǎn) = 2k + 1，右子節(jié)點(diǎn) = 2(k + 1)，最大堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn)，最小堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)。

在一個(gè)長(zhǎng)為n的序列，堆排序的過(guò)程是從第n/2開(kāi)始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(最大堆)或者最小(最大堆)，這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n/2-1，n/2-2，… 1 這些個(gè)父節(jié)點(diǎn)選擇元素時(shí)，就會(huì)破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過(guò)去了，而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒(méi)有交換，那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法。