前一章的“概率分析與隨機算法”實在傷腦子，好在看過去了，現在正在看的是排序部分；

堆排序，這次說的是最大推排序（和最小堆原理也是相同的，最小堆實現），和原文中的思路也是一樣的，後序有補充也會貼出來的；

最大堆...即是父節點的值大於孩子的值，若不滿足條件，則經過調節使其滿足條件：

維護堆：

書本中的偽碼：

思想則是訪問父節點，若是存在孩子節點的值大於父節點的值，則將最大的孩子節點的值與父節點進行交換，為了避免交換後的節點繼續不滿足條件，再次調用函數，使其滿足條件，如對以下節點（不清晰部分為4）：

其中父節點3,4,5皆滿足條件，到2父節點時，不滿足最大堆，即進行調節：

此時則發現節點4又不滿足條件了，繼續調節：

調節的過程就是這樣；

建堆：

我們知道，當用數組來存儲n個元素的堆時，葉子節點的下標是[n / 2] + 1，[n / 2] + 2......n。如上中10個元素，6之後即為葉子節點；

這時建堆即可：

由n / 2開始向第一個元素進行建堆；

堆排序：

先構建一個最大堆，最後不斷的將根節點提取出來，同時不斷調節余下的節點保證是最大堆；

貼下代碼：

#include 
#include 

using namespace std;

void MaxHeapIfy(int A[], int length, int i)  //維護
{
    int left = i * 2;  //節點i的左孩子
    int right = i * 2 + 1; //節點i的右孩子節點
    int largest = i;  //默認父節點

    if (left <= length && A[largest] < A[left])  //左孩子比父節點大
    {
        largest = left;
    }

    if (right <= length && A[largest] < A[right])  //右孩子最大
    {
        largest = right;
    }

    if (i != largest)   //最大值不是父節點
    {
        int temp = A[largest]; //exchange
        A[largest] = A[i];
        A[i] = temp;

        MaxHeapIfy(A, length, largest);  //繼續維護
    }
}

void BuildMaxHeap(int A[], int length)  //建堆
{
    for (int i = length / 2; i >= 1; i--)
    {
        MaxHeapIfy(A, length, i);
    }
}

void HeapSort(int A[], int length)  //堆排
{
    int temp;

    BuildMaxHeap(A, length);      //建堆

    /*
    cout<<"建堆情況：";  //
    for(int i = 1; i <= length; i++)
        cout<