??
目錄
- 1、堆的概念
- 2、實現堆排序前的準備工作
- 3、堆排序的思路
- 3.1 第一步
- 3.2 第二步
- 4、結語
1、堆的概念
??在了解堆排序之前我們先要了解什么是堆：一個按照完全二叉樹的儲存方式存儲的一維數組我們稱之為堆。
??而堆又可以分為大堆和小堆。
??大堆：二叉樹中的父結點在數值上都比子結點大。
??小堆：二叉樹中的父結點在數值上都比子結點小。
??下圖在就是一組較為明顯的大小堆。
??故堆排序就是在堆的前提下進行排序。
2、實現堆排序前的準備工作
??我們需要完成的準備工作是實現一個關于二叉樹即堆的向下調整函數，此處我們寫為HeapAdjustDown。
void Swap(int* p1,int* p2) //簡單的交換函數
{int* tmp = *p1;*p1 = *p2;*p2 = tmp;
}void HeapAdjustDown(int* a,int n,int parent)//a代表數組的地址，n為數組元素個數，parent為當前元素所在下標。
{int child = parent * 2 + 1; //假設左孩子大于或小于右孩子.while(child < n) //結束條件為到達最后一層時，最后一層沒有子。{if(child + 1 < n && a[child + 1] > a[child])//判斷左孩子是否真的大于或小于右孩子，如果不是{ //讓child代表右邊孩子的下標。++child;}if(a[child] > a[parent]) //判斷父與子的關系，如果父大于或小于子，讓其交換位置。{Swap(&a[child],&a[parent])parent = child; //此處令交換的子的下標成為新的parent下標，即沿著交換路徑一致進行//比較，直至到達最后一層。child = parent * 2 + 1;}else{break; //當不滿足大小條件是就會進來，即已經按照需求將堆排列成了大堆或者小堆。}}
}
??上面就是我們所完成的準備工作，其中
if(child + 1 < n && a[child + 1] < a[child])
if(a[child] < a[parent])
??這兩條判斷語句中的數組內成員比較可以更換比較符號。
??當使用 “ < ” 號時，第一條判斷依據所篩選的時兩個子中較小的一個。
?????????? 第二條判斷語句就是比較所選的子是否小于父，如果小于就進行交換。
?????????? 這樣進行調整后的堆就稱之為小堆，即父皆比子小。
??當使用 “ > ” 號時，第一條判斷依據所篩選的時兩個子中較大的一個。
?????????? 第二條判斷語句就是比較所選的子是否大于父，如果大于就進行交換。
?????????? 這樣進行調整后的堆就稱之為大堆，即父皆比子大。
3、堆排序的思路
3.1 第一步
??我們首先要做的就是將得到的數組進行調整，將其調整為大堆或者小堆。
??故寫一個函數來進行操作較為方便：HeapSort
void HeapSort(int* a,int n)//此處的n為數組的元素個數
{for(int i = (n - 1 - 1) / 2; i >= 0; i--)//此處為何從(n - 1 - 1) / 2開始，后面會有圖解，耐心一點哦~{//然后調用我們的向下調整函數。HeapAdjustDown(a,n,i);}
}
??到這里后，我們就完成了對數組的大堆或者小堆化，此處我們所進行的是大堆化處理。
??下面就進行我們此截止到目前的看圖說話：
??假設我們所擁有的數組是{1，3，5，7，9，2，4，6，8，10}。
??其在數組中和在堆中的存放方式如上圖所示，我們按照上述代碼執行。
??而后我們在數組元素9的基礎上進行向下調整。
??這一步進行完后，我們的i–，此時的i = 3，也就是我們的元素7所在下標，故此時在數組元素7的基礎上向下調整。
??故循環的意義就是從最后一層的父開始進行向下調整，一致循環到根位置，后面我們直接展示過程圖，不在進行比較講解。
??到此處我們的大堆構建也算完成了。
??根據VS驗證我們所進行的數組大堆化也是正確無誤的。
??此處又會有看官提出問題，我們為什么不從數組的頭部開始進行向下調整呢，反而從尾部開始呢？
??我們直接上圖，當我們從頭部開始時，進行向下調整，得到的卻不是大堆。這是因為：
??而后我們也同樣直接展示過程圖：
??至此我們所得到的新數組也就和上述實驗數組結果一致，為{5，9，4，8，10，2，1，6，7，3}。
??總而言之，我們不從頭部開始進行向下調整，是因為以這樣的方式進行時，每一次調整只會調整當前位置及當前位置向后的數據，而不會向前進行比較，會造成不可避免地bug。
3.2 第二步
??我們將數組大堆或小堆化后，就可以進行排序了，此時我們進行的是升序排列，排序的代碼如下：
void HeapSort(int* a,int n)//此處的n為數組的元素個數
{for(int i = (n - 1 - 1) / 2; i >= 0; i--)//此處為何從(n - 1 - 1) / 2開始，后面會有圖解，耐心一點哦~{//然后調用我們的向下調整函數。HeapAdjustDown(a,n,i);}int end = n - 1; //原理下文解釋while(end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}
??我們可以看到代碼中創建了一個變量 “ end ”，其代表的含義為最后一個元素的數組下標，我們在前文中已經將數組進行了大堆化，故我們數組的第一個元素是大于其他元素的。
??此時我們將第一個數和最后一個數據交換位置，這樣最大的數就處在了末尾，然后按照同樣的方式對前面九個數字進行大堆化，這樣就又會有一個第二大的數字排列在第一位，然后進行下一次循環，然后我們將 end–，進入下一次循環。下面我們展示過程圖，并不在對途中內容進行講解：
??依次向下進行最終就得到了如下的數組。
??通過驗證我們可以得到上述方法是可行且正確無誤的。
??從中我們也可以發現一個規律，我們通過創建大堆可以得到升序的序列，通過類比，我們明白也可以通過創建小堆可以得到降序的序列。
4、結語
??十分感謝您觀看我的原創文章。
??本文主要用于個人學習和知識分享，學習路漫漫，如有錯誤，感謝指正。
??如需引用，注明地址。
