對排序的實現思路有兩種
第一種：1.構建最小堆。2.將最小堆的堆頂元素取出放到輔助數組的0號下標。3.重新調整成最小堆（向上調整） 4.重復2-3
第二種：1.構建最大堆。2.將堆頂元素（0號）與最後一個元素調換位置。3.最後一個元素不變，剩下的數據調整成最大堆。 4.重復2-3。
這裡用的是第二種方式。
幾點說明：
1.構建堆用的是數組來存儲，即堆頂為s[0],第一層為s[1],s[2]以此類推。
2.下面的程序可能存在bug，因為是筆者用一組寫在代碼裡面的數組來測試的。旨在說明問題。
3.為了方便，所有函數的參數都傳進數組，直接在數組上做位置調整（對於數組來說，似乎也只能這麼做）。
4.堆排序應該是 heap sort 英語沒學好真是悲哀。
直接上代碼：
//Sort.h 不好意思寫成了頭文件
#include<iostream>
using namespace std;
int Max(int s[],int a,int b)//取兩數中較大的數的下標
{
return s[a]>s[b]?a:b;
}
/*
int Min(int s[],int a,int b)
{
return s[a]<s[b]?a:b;
}
*/
void swap(int s[],int a,int b)//交換兩個數的位置
{
int temp;
temp = s[a];
s[a]=s[b];
s[b] = temp;
}
void FixDown(int s[],int a,int n)//向下調整算法
{
int temp = a;//這句沒什麼用，既然寫在這裡了就不刪掉了。
int max = Max(s,temp*2+1,temp*2+2);//取最大值，在下面用到
if(s[temp]>=s[max]||(temp*2+2)>n||(temp*2+1)>n)//如果已經是局部（以s[temp]為根的）最大堆，或者s[temp]是葉子節點，直接返回
return;
if(s[temp]<s[max])//否則如果不是局部最大堆，調整。
{
swap(s,temp,max);//交換s[temp]和其葉子節點中較大的那個的數據。（如果不是最大那個的話調整完了還不是最大堆，而程序不會察覺）
FixDown(s,max,n);//遞歸
}
}
void Head(int s[],int n)//構造最大堆，只在一開始的時候用，其實也是調用向下調整算法
{
for(int i=(n-1)/2;i>=0;i--)//注意這裡循環。向下調是從倒數第二層不斷網上調整的。
{
FixDown(s,i,n-1);
}
}
void HeadSort(int s[],int n)//排序
{
Head(s,n);//=====注意：創建最大堆（把數組裡面的元素重排）
int j=n-1;//數組尾部
while(j>0)
{
if(s[0]>s[j])//這句主要是最後一次的時候用。沒有if也沒關系
{
swap(s,0,j);//調換
FixDown(s,0,j-1);//向下調整。注意此時調整的最後一個元素是temp[j-1],不會訪問到j，也就是說j被固定了。
}
j--;
}
}
void Sort(int s[],int low,int high)//sort函數，外部接口，可以忽視。因為裡面其實就是一條語句，調用上面的函數
{
HeadSort(s,high);
}
void Show(int s[],int n)
{
for(int i=0;i<n;i++)
cout << s[i] << " ";
}
下面是測試文件
#include"Sort.h"
int main()
{
//int s[]={1,23,3,45,23,5,6,741,2,8,561,395,123,5110};
int s[] = {1,2,3,4,5,6,7,8,9,10};
int n = 10;
Sort(s,0,n);
cout << "排序後：";
Show(s,n);
return 0;
}
程序的運行過程是這樣子的：
1.數組傳進來，調用Sort函數。之所以寫成這麼函數，是因為以後寫別的排序算法的時候，在裡面調用就可以了，練練自己程序擴展的用法。
2.調用堆排序函數--》Headsort函數 《----算法從這裡開始
3.先把數組調整成最大堆==》Head函數
4.現在拿到最大堆之後，s[0]跟s[j]換（j=n-1）。重新調整，循環。
完成。
補充：關於向下調整，如果上面講的不清楚，可以找相應的博客來看，那種帶圖片分析的，一看就懂。
C++ Primer Plus 第6版 中文版 清晰有書簽PDF+源代碼 http://www.linuxidc.com/Linux/2014-05/101227.htm
讀C++ Primer 之構造函數陷阱 http://www.linuxidc.com/Linux/2011-08/40176.htm
讀C++ Primer 之智能指針 http://www.linuxidc.com/Linux/2011-08/40177.htm
讀C++ Primer 之句柄類 http://www.linuxidc.com/Linux/2011-08/40175.htm
將C語言梳理一下，分布在以下10個章節中：