基礎堆排序和 Heapify

這一節(jié)我們介紹兩個使用堆或者說基于堆的思想進行排序的算法窟感。

思路1：一個一個地往最大堆里面放元素，然后再一個一個地取出歉井，倒序放置于一個空數組中柿祈，就完成了元素的排序；

思路2：一次性把整個數組復制到一個新數組哩至，通過新數組 heapify 操作谍夭，使得新數組成為一個最大堆，然后再一個一個地取出憨募，倒序放置于一個空數組中紧索，就完成了元素的排序。

思路1：一個一個放進最大堆菜谣，再一個一個地取出完成排序

我們首先要明確的是珠漂，堆排序的時間復雜度是 。

我們可以從以下幾個維度進行不同算法性能的比較尾膊，對數量級是 100 萬個元素的數組進行排序媳危。

使用的排序算法維度：歸并排序，快速排序冈敛，三路快速排序待笑，堆排序（借助額外空間的堆排序）。

元素特點維度：1抓谴、隨機暮蹂；2寞缝、近乎有序；3仰泻、含有大量相同元素的數組荆陆。

Java 代碼：

/**
 * 第 1 個版本的堆排序算法
 * Created by liwei on 17/5/15.
 */
public class HeapSort1 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "第 1 個版本的堆排序算法";
    }

    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        MaxHeap maxHeap = new MaxHeap(length);
        for (int i = 0; i < length; i++) {
            maxHeap.insert(arr[i]);
        }
        for (int i = length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }
}

我們在上一小節(jié)，介紹了將一個元素 insert 到最大堆中集侯，和從最大堆中取出一個元素被啼，僅僅通過這兩個操作，就可以完成排序任務棠枉。方法很簡單浓体，把待排序數組中的元素全部 insert 到最大堆里，然后再一個一個取出來辈讶，因為我們要按照升序排序命浴，因此從后向前放置從最大堆中拿出的元素。

這個方法有一個缺點荞估，那就是要使用和數組元素個數相等的最大堆空間，即空間復雜度是 稚新。

而這一節(jié)我們要介紹的是一種直接使用堆排序的 sink 方法完成排序任務的方法勘伺，這種方法僅使用 的空間復雜度，用于一個臨時表變量的存儲褂删。

首先飞醉，我們介紹一個操作，名為 heapify 屯阀。

思路2：一次性復制數組元素到新的數組缅帘，新數組自我調整成最大堆

什么是 Heapify

Heapify 是嘗試將一整個數組構建成一個堆的方式，即通過調整自己难衰，交換數組中的元素钦无，就可以把自己整理成一個最大堆。

理解 Heapify 關鍵的部分

1盖袭、所有的葉子結點就是一個最大堆失暂，此時每個堆中的元素只有1個；

2鳄虱、當我們的索引從 1 開始計數的前提下弟塞，第 1 個非葉子的結點的索引是 index/2（自己畫一個圖，就可以看清楚這個規(guī)律拙已，我們可以使用數學歸納法來證明）决记，如何讓它滿足堆的性質呢？ Shift Down 就可以了倍踪。
思考：我們?yōu)槭裁床挥?Shift Up系宫？
我的思考如下：如果使用 Shift Up 的話索昂，那就得將數組中所有的元素都 Shift Up，相比于只用一半的元素 Shift Down 而言笙瑟，工作量會少很多楼镐。

3、從 index/2 遞減到根（index==1的時候）依次去完成 Shift Down往枷，一開始就排除了 length/2 這么多元素框产。

heapify

使得一個數組是堆有序的操作就叫做“heapify”。具體的做法是：從最后一個非葉子結點開始到索引為 的位置错洁，逐個 sink秉宿。

在上一步“堆排序”中，我們注意到屯碴，有這樣一個操作“把待排序數組按順序放入一個堆（入隊）”描睦，這一步得一個接著一個按照順序放入堆中，實際上导而，可以通過一個稱之為 heapify 的操作忱叭，讓這個數組自行調整成一個最大堆，即使之“堆有序”今艺，而此時無需借助 空間就完成了最大堆的構建韵丑。事實上，只需對數組中一半的元素執(zhí)行 shift down 就可以了虚缎。

以下代碼還是使用了 空間撵彻，主要是為了說明 heapify。

heapify 如下所示：從索引的 self.count // 2 位置開始实牡，直到索引為 的元素結束陌僵，逐個下沉，就可以讓一個數組堆有序创坞。

說明：索引的 self.count // 2 位置是從下到上第 1 個非葉子結點的索引

Python 代碼：

class MaxHeap:
    def __init__(self, nums):
        self.capacity = len(nums)
        self.data = [None] * (self.capacity + 1)
        self.count = len(nums)
        self.__heapify(nums)

    def __heapify(self, nums):
        # 挨個賦值
        for i in range(self.capacity):
            self.data[i + 1] = nums[i]
        for i in range(self.count // 2, 0, -1):
            self.__sink(i)

Java 代碼：

/**
 * 傳遞一個數組碗短，形成一個最大堆
 * 理解 heapify 是關鍵
 *
 * @param arr 待排序的數組元素
 */
public MaxHeap(int[] arr) {
    int length = arr.length;
    data = new int[length + 1];
    for (int i = 0; i < length; i++) {
        data[i + 1] = arr[i];
    }
    // 添加一個元素，就要把 count 加 1 题涨，因為我們是一次性添加豪椿，所以就直接將 count 賦值為 length 就可以了
    // 這一步賦值千萬別忘了
    count = length;
    // 理解這一步是關鍵 heapify
    for (int i = length / 2; i >= 1; i--) {
        shiftDown(i);
    }
}

這樣，我們就可以寫出我們的第 2 個使用堆排序的算法了携栋，直接把數組傳到最大堆這個數據結構里面搭盾。

heapify 以后挨個取出來，倒著放回去婉支，也可以完成排序鸯隅，就不用一個一個放進去，做上浮的操作了。整體上排序會比一個一個放進去快一些蝌以。

Java 代碼：通過 heapify 將數組重組成最大堆實現的排序

/**
 * 第 2 個版本的堆排序算法
 * Created by liwei on 17/5/15.
 */
public class HeapSort2 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "第 2 個版本的堆排序算法";
    }

    @Override
    public void sort(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        int length = arr.length;
        for (int i = length - 1; i >= 0; i--) {
            arr[i] = maxHeap.extractMax();
        }
    }
}

重要結論：堆排序在整體上的性能不如歸并排序和快速排序炕舵。但是，堆這種數據結構更多的時候用于動態(tài)數據的維護跟畅。

一個數學結論：將 個元素逐一插入到一個空堆中咽筋，時間復雜度是 。Heapify 的過程徊件，時間復雜度是 奸攻。

HeapSort2 會快一點的原因是：一上來我們從 n/2 這個地方開始，逐一操作虱痕，排除了 n/2 個元素睹耐，所以效率肯定比第 1 種好。

可是這兩種基于堆的排序算法部翘，我們在堆排序的過程中硝训，使用了額外的空間（即 MaxHeap 中的數組），使用了 的空間復雜度新思。那么不借助額外的空間是不是也可以完成堆排序呢窖梁？這就是我們下一節(jié)要介紹的內容——原地堆排序。

原地堆排序

通過上一節(jié)的學習夹囚，我們知道一個數組通過 heapify 操作纵刘，即通過一半的元素執(zhí)行 Shift Down 的操作可以逐漸地整理成一個最大堆。

我們把“原地堆排序”拆解為以下 3 個部分：

1崔兴、首先彰导，轉換思維蛔翅，堆從索引 開始編號敲茄；

代碼很多地方都要改，好在并不復雜山析，正好可以幫助我們復習堆的 sink 操作堰燎，如果只是用于排序任務，不需要 swim 操作笋轨；

2秆剪、 sink 操作要設計成如下的樣子，設計一個表示 end 的變量爵政，表示待排序數組的 [0, end]（注意是閉區(qū)間）范圍是堆有序的仅讽。

上一節(jié)我們將一個數組通過 heapify 的方式逐漸地整理成一個最大堆。而原地堆排序的思想是非常直觀的钾挟，從 shift down 的操作我們就可以得到啟發(fā)洁灵，堆中最大的那個元素在數組的 0 號索引位置，我們把它與此時數組中的最后一個元素交換掺出，那么數組中最大的元素就放在了數組的末尾徽千，此時再對數組的第一個元素執(zhí)行 shift down苫费，那么 shift down 操作都執(zhí)行完以后，數組的第 1 個元素就存放了當前數組中的第 2 大的元素双抽。依次這樣做下去百框，就可以將一個數組進行排序。

理解這個原理的關鍵之處：對堆頂元素執(zhí)行了 Shift Down 操作以后牍汹，就會把這個堆中的最大的元素挪到堆頂铐维。

此時，因為用到了索引柑贞，并且須要用到索引為 的數組元素方椎，因此我們就要將最大堆中數組的索引從 開始計算，重新寫一套堆的 API钧嘶。

我們整理一下棠众，其實這個思想跟“選擇排序”是一樣的，只不過我們每一輪選出一個當前未排定的數中最大的那個有决，即“選擇排序”+“堆”就是“堆排序”闸拿。

image

“堆排序”代碼實現的注意事項：

1、此時最大堆中數組的索引從 開始計算书幕。與之前索引從 開始的最大堆實現比較新荤，性質就發(fā)生了變化，但并不會不好找台汇，我們可以自己在紙上畫一個完全二叉樹就可以很清晰地發(fā)現規(guī)律：苛骨，，苟呐，最后一個非葉子結點的索引是：痒芝；

2、原地堆排序牵素，因為索引從 號開始严衬，相應的一些性質在索引上都發(fā)生變化了；

3笆呆、注意到我們只有 shift down 的操作请琳，對于 shift down 的實現，一些細節(jié)就要很小心赠幕，shift down 是在一個區(qū)間內進行的俄精，我們在設計新的 shift down 方法的實現的時候，應該設計待排序數組區(qū)間的右端點榕堰。

Python 代碼：

def __sink(nums, end, k):
    # end ：數組 nums 的尾索引竖慧，
    # __sink 方法維持 nums[0:end]，包括 nums[end] 在內堆有序
    assert k <= end
    temp = nums[k]
    while 2 * k + 1 <= end:
        # 只要有孩子結點：有左孩子，就要孩子結點
        t = 2 * k + 1
        if t + 1 <= end and nums[t] < nums[t + 1]:
            # 如果有右邊的結點测蘑，并且右結點還比左結點大
            t += 1
        if nums[t] <= temp:
            break
        nums[k] = nums[t]
        k = t
    nums[k] = temp


def __heapy(nums):
    l = len(nums)
    for i in range((l - 1) // 2, -1, -1):
        __sink(nums, l - 1, i)


def heap_sort(nums):
    l = len(nums)
    __heapy(nums)

    for i in range(l - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        __sink(nums, i - 1, 0)

Java 代碼：

/**
 * 原地堆排序
 * Created by liwei on 17/5/15.
 */
public class HeapSort3 implements ISortAlgorithm {
    @Override
    public String getName() {
        return "原地堆排序";
    }


    /**
     * 原地堆排序的目標就是灌危，不再借助 MaxHeap 這個數據結構進行排序，減少了空間復雜度
     * 注意：此時我們的數組索引從 0 開始定義(自己在紙上畫一下圖碳胳，就能清晰地明白算法實現的含義)
     *
     * @param arr 待排序數組
     */
    @Override
    public void sort(int[] arr) {
        int length = arr.length;
        // 將一個無序的數組組成了一個最大堆勇蝙，第 1 個元素就是最大值
        for (int i = (length - 1) / 2; i >= 0; i--) {
            shiftDown(arr, length, i);
        }
        
        // 代碼邏輯非常簡單明確，完全可以自己寫出來
        // 
        for (int i = length - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }


    /**
     * 從索引為 0 開始挨约，up 為止 [0,up] 的數組元素進行 shift down 的操作
     *
     * @param arr 
     * @param up 這里的 up 定義為形成堆這個數據結構的最大下標（從索引 0 就放元素）味混，
     *           即在區(qū)間 [0,up] 范圍內 Shift Down
     * @param index 對索引是 index 的元素執(zhí)行 Shift Down 操作
     */
    private void shiftDown(int[] arr, int up, int index) {
        // 如果有右孩子的結點，并且右孩子結點比左孩子結點的值要大
        // 此時可以忽略左孩子結點的存在诫惭，拿右孩子結點的數值和自己比較

        // 只要它有左孩子翁锡，就不是葉子結點，就可能 shift down夕土，注意：這里是小于號
        while (2 * index + 1 < up) {
            int j = 2 * index + 1;
            if (j + 1 < up && arr[j] < arr[j + 1]) {
                j = j + 1;
            }
            if (arr[index] < arr[j]) {
                swap(arr, index, j);
                index = j; // 留意
            } else {
                break;
            }
        }
    }

    private void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

}

說明：首先進行一次 heapify 的過程：從索引為 的結點開始執(zhí)行 Shift Down馆衔。heapify 過程的代碼框架幾乎是套路，一定要熟悉怨绣，只不過我們要弄清楚角溃，我們的最大堆是從索引為 的位置開始存放元素，還是從索引為 的地方開始存放元素篮撑。

// 將一個無序的數組組成了一個最大堆减细，第 1 個元素就是最大值
for (int i = (length - 1) / 2; i >= 0; i--) {
    shiftDown(arr, length, i);
}

到此為止，堆的排序算法就已經介紹完了赢笨，下面我們對之前學習過的排序算法作一個總結未蝌。

排序算法總結

平均時間復雜度

時間復雜度分為平均時間復雜度、最好時間復雜度和最壞時間復雜度茧妒。對于一個算法來說萧吠，往往有很多特殊情況，一般而言嘶伟，我們所說的時間復雜度都指最壞時間復雜度怎憋。

對我們學習過的各種排序算法的總結和對比

快速排序相對會更快一些又碌。一般系統級別的排序九昧，是用快速實現的。如果有大量重復鍵值毕匀，可以使用三路快排铸鹰。

排序算法的穩(wěn)定性

查資料了解什么是排序算法的穩(wěn)定性≡聿恚可以通過自定義比較函數蹋笼，讓排序算法不存在穩(wěn)定性問題。系統級別的排序算法，如果要求穩(wěn)定性的話剖毯，一般使用歸并排序圾笨。

對未來的探索

是不是存在一種神秘的排序算法？讓所有指標達到最優(yōu)呢逊谋。liuyubobobo 老師告訴我們擂达，目前還沒有。

本文源代碼

Python：代碼文件夾胶滋，Java：代碼文件夾板鬓。

（本節(jié)完）