八大排序算法詳解——堆排序

2019-11-10 17:17:51

字體：大中小

來源：轉載

供稿：網友

基本思想

堆的定義

n個關鍵字序列kl，k2，…，kn稱為堆，當且僅當該序列滿足如下性質之一（簡稱堆性質）：

ki≤k2i且ki≤k2i+1 或ki≥k2i且ki≥k2i+1（1≤i≤FLOOR(n/2)）

若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。

小根堆：根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最小的。大根堆：根結點（亦稱為堆頂）的關鍵字是堆里所有結點關鍵字中最大的。

我們可以選擇大根堆或者小根堆中的任意一個來進行排序。

排序思想

用大根堆排序的基本思想：

先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區。再將關鍵字最大的記錄R[1]（即堆頂）和無序區的最后一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key。由于交換后新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然后再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最后一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系 R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。

算法實現

堆排序算法，java實現，代碼如下所示：

public abstract class Sorter { public abstract void sort(int[] array); } public class HeapSorter extends Sorter { public void sort(int[] array) { heapSort(array); } /** * <p>堆排序方法 * <p>基于大根堆的堆排序方法 */ PRivate void heapSort(int[] array) { Integer tmp; // 用于交換的暫存單元 buildHeap(array); // 執行初始建堆，并調整 for (int i = 0; i < array.length; i++) { // 交換堆頂元素array[0]和堆中最后一個元素array[array.length-1-i] tmp = array[0]; array[0] = array[array.length - 1 - i]; array[array.length - 1 - i] = tmp; // 每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調整 adjustHeap(array, 0, array.length - 1 - i); } } /** * 建堆方法 * 調整堆中0~array.length/2個結點，保持堆的性質 * */ private void buildHeap(int[] array) { // 求出當前堆中最后一個存在孩子結點的索引 int pos = (array.length - 1) / 2; // 從該結點結點開始，執行建堆操作 for (int i = pos; i >= 0; i--) { adjustHeap(array, i, array.length); // 在建堆過程中，及時調整堆中索引為i的結點 } } /** * <p> * 調整堆的方法 * * @param s 待調整結點的索引 * @param m 待調整堆的結點的數量(亦即：排除葉子結點) */ private void adjustHeap(int[] array, int s, int m) { Integer tmp = array[s]; // 當前待調整的結點 int i = 2 * s + 1; // 當前待調整結點的左孩子結點的索引(i+1為當前調整結點的右孩子結點的索引) while (i < m) { if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比當前待調整結點大的孩子結點) i = i + 1; } if (array[s] < array[i]) { array[s] = array[i]; // 孩子結點大于當前待調整結點，將孩子結點放到當前待調整結點的位置上 s = i; // 重新設置待調整的下一個結點的索引 i = 2 * s + 1; } else { // 如果當前待調整結點大于它的左右孩子，則不需要調整，直接退出 break; } array[s] = tmp; // 當前待調整的結點放到比其大的孩子結點位置上 } } }

排序過程

假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。

第一步：初始建堆首先執行的初始建堆（在建堆的過程中需要調整堆）。過程如下：

求出當前堆中最后一個存在孩子結點的索引

這里，把數組array看做是一棵完全二叉樹，這樣數組每個索引位置上的元素都對應到二叉樹中的結點，如圖所示： heapsort 其中需要在這棵樹中找到最后一個有孩子最大的一個結點的索引：pos = (array.length-1)/2 = (20-1)/2 = 9也就是索引為9的array[9] = 76，由后至前層次遍歷，從array[9]一直到array[0]，對初始堆進行調整。

對初始堆進行調整調整結點array[9] = 76：

先比較array[9] = 76的左右孩子：s = 9，i = 2*s+1 = 2*9 + 1 = 19，而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array[9] = 76沒有右孩子)，只需要將array[9] = 76與array[i] = array[19] = 49比較，因為array[9] = 76>array[i] = array[19] = 49，則不需要交換array[9] = 76與array[i] = array[19] = 49，繼續對下一個結點（也就是array[8] = 55）進行調整；

調整結點array[8] = 55：

先比較array[8] = 55的左右孩子：s = 8，i = 2*s+1 = 2*8 + 1 = 17,，而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array[8] = 55存在右孩子)，左孩子array[i] = array[17] = 65小于右孩子array[i+1] = array[18] = 76，只需要將array[8] = 76與右孩子array[i+1] = array[18] = 76比較，因為array[8] = 55<array[i+1] = array[18] = 76，則需要交換array[8] = 55與array[i+1] = array[18] = 76，交換后如圖所示： heapsort-1 繼續對下一個結點（也就是array[8] = 55）進行調整；

調整結點array[7] = 37：

顯然，不需要交換；

調整結點array[6] = 0：

調整結果如圖所示： heapsort-2

調整結點array[5] = 9：

調整結果如圖所示： heapsort-3

調整結點array[4] = 26：

調整結果如圖所示： heapsort-4

調整結點array[3] = 76：

顯然，不需要交換。

調整結點array[2] = 34：

調整結果如圖所示： heapsort-5

調整結點array[1] = 12：

調整結果如圖所示： heapsort-6

調整結點array[0] = 94：

顯然，不需要交換。

至此，對初始堆的調整完成。

第二步：第一次交換將堆頂元素與最后一個元素交換，即array[0] = 94與最后一個元素array[19] = 49交換，如圖所示： heapsort-7 此時，數組為：array = {49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94}數組中最大的元素被交換到了數組的末尾，也就是array[19] = 94是最終排好序的固定位置。