堆排序
堆排序顧名思義，就是使用堆這種資料結構進行排序，什么是堆呢，堆(Heap)是計算機科學中一類特殊的資料結構的統稱，堆通常是一個可以被看做一棵完全二叉樹的陣列物件，
堆總是滿足下列性質：
堆中某個結點的值總是不大于或不小于其父結點的值；
堆總是一棵完全二叉樹，
將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆，
使用堆排序，第一步是將無序序列結構轉變為一個大頂堆或者小頂堆，然后將堆頂元素與末尾元素進行交換，使末尾元素最大，然后繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素，如此反復，直到排列完成，
代碼
void max_heapify(int arr[], int start, int end)
{
//獲得父節點下標和子節點下標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子節點下標在范圍內才做比較，子節點下標不能大于陣列最大下標
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函式
return;
else //否則交換父子內容再繼續子節點和孫節點比較
{
int temp = arr[son];
arr[son] = arr[dad];
arr[dad] = temp;
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
int i;
//初始化，i從最后一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--) {
max_heapify(arr, i, len - 1);
}
//先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
for (i = len - 1; i > 0; i--)
{
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 8,4,7,1,5,3,0,9 };
heap_sort(arr, 8);//陣列和長度
return 0;
}
分析代碼
1.如何算出最后一個父節點（len/2-1為什么是最后一個父節點），
觀察在最左邊的數，0，1，3，7，不難發現，后一個數等于前一個數*2+1
所以當父節點為n時，子節點應為2n+1 和2n+2兩個，
設陣列長度為n，最后一個非葉子節點為i，
分兩種情況：
①只有左孩子，則n-1為左孩子節點下標，有n-1 = 2i + 1，得i = [(n-1)-1]/2 = n/2-1，
②有左孩子和右孩子，則n-2為左孩子節點下標，n-1為右孩子節點下標，
有 n-2 = 2i+1，得i = [(n-2)-1]/2 = (n-1)/2 -1，
有 n-1 = 2i+2，得i = [(n-1)-2]/2 = (n-1)/2 -1，
當陣列長度為偶數時，符合第一種情況，父節點為n/2-1，
當陣列長度為奇數時（這個奇數一定比第一種情況的偶數大），符合第二種情況，父節點為(n-1)/2 -1，但是由于強型別語言的特征，除不整，將向下取整，(n-1)/2 -1將等于n/2-1，
舉個例子：
8/2-1 = 3
9/2-1 = 3
所以，圖中的堆，最后一個父節點為3，之后的2，1，0，分別對應之后的父節點，下面的代碼分別是遍歷3，2，1，0四個父節點進行操作，轉變為大頂堆或者小頂堆，
for (i = len / 2 - 1; i >= 0; i--) {
max_heapify(arr, i, len - 1);
}
2.分析代碼中max_heapify()函式找到父節點之后，如何找到交換元素
//拿圖中所示的堆舉例
//獲得父節點下標和子節點下標，最后一個父節點是3
int dad = start; //3
int son = dad * 2 + 1; //7 只考慮左孩子，因為左孩子一定存在
while (son <= end) //若子節點下標在范圍內才做比較，子節點下標不能大于陣列最大下標
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//如果son + 1小于等于陣列最大下標，說明有右孩子，且判斷左右兩個孩子大小，如果右孩子比左孩子大，則將子節點改為右孩子，
son++;
if (arr[dad] > arr[son]) //判斷最大孩子和父節點的大小，如果父節點大，則回傳
return;
else //否則交換父子內容，然后再繼續比較
{
int temp = arr[son];
arr[son] = arr[dad];
arr[dad] = temp;
//再繼續子節點和孫節點比較，直到son不滿足<=end
dad = son;
son = dad * 2 + 1;
}
}
CSDN認證博客專家
Qt
C
C++
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/260652.html
標籤：區塊鏈
上一篇：理財入門：REITs(簡述)