堆排序是一種比較常用的排序方式，具有O(NlogN)的時(shí)間復(fù)雜度，它只需要一個(gè)記錄大小的空間，算法的核心是“篩選”。
堆的存儲(chǔ)方式是一維數(shù)組，因?yàn)樗且豢猛耆鏄?shù)，孩子與雙親下標(biāo)有簡(jiǎn)單直接的計(jì)算方式（數(shù)組下標(biāo)從１開(kāi)始）：節(jié)點(diǎn)i的左孩子下標(biāo)為2 * i，右孩子下標(biāo)為2 * i + 1，雙親節(jié)點(diǎn)下標(biāo)為i / 2
堆排序的過(guò)程可分為兩步：
1.建立堆（經(jīng)過(guò)n / 2次“篩選”，n為節(jié)點(diǎn)總個(gè)數(shù)）
2.不斷讓堆頂元素與堆的最后一個(gè)未排序的元素交換，并進(jìn)行“篩選”，以維持堆的性質(zhì)（該過(guò)程進(jìn)行n - 1次后排序完成）。
下面我們以int型數(shù)組為例，通過(guò)建立大頂堆將數(shù)組a[]中的元素按升序排序。以下是算法代碼，其中f()是篩選函數(shù)，完成一次篩選。

 1int main()
 2{
 3    int i, j;
 4    int a[] = {0, 1, 5, 95, 7, 3, 8, 0, 90, 25, 13};
 5    int n = 10;
 6    for(i = n / 2; i > 0; i--)//從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，建立大頂堆
 7    {
 8        f(a, i, n);
 9    }
10    for(i = n; i > 1; i--)//經(jīng)過(guò)n - 1次交換、篩選后，完成排序。
11    {
12        swap(&a[1], &a[i]);
13        f(a, 1, i - 1);
14    }
15    //out
16    for(i = 1; i <= n; i++)
17        printf("%3d", a[i]);
18    putchar(10);
19    system("pause");
20}

以下是不同版本的篩選函數(shù)f()
void f(int *a, int top, int r)
 a為待排序數(shù)組，
 top是堆頂
 r是堆的最后一個(gè)元素
第一個(gè)是我寫的，很原始：

 1void f(int *a, int top, int r)
 2{
 3    int i = top;
 4    int lt = 2 * i;
 5    int rt = 2 * i + 1;
 6    while(lt <= r && (a[lt] > a[i] || (rt <= r && a[rt] > a[i])))
 7    {
 8        if(rt <= r)
 9        {
10            if(a[lt] > a[rt])
11            {
12                swap(&a[lt], &a[i]);
13                i = lt;
14            }
15            else
16            {
17                swap(&a[rt], &a[i]);
18                i = rt;
19            }
20        }
21        else
22        {
23            swap(&a[lt], &a[i]);
24            i = rt;
25        }
26        lt = 2 * i;
27        rt = 2 * i + 1;
28    }
29}

第二個(gè)是書上的，很簡(jiǎn)潔：

 1void f(int *a, int top, int r)
 2{
 3    int j;
 4    for(j = 2 * top; j <= r; j *= 2)//j初始為左孩子
 5    {
 6        if(j < r && a[j] < a[j + 1]) //如果右孩子存在且比左孩子大
 7            j++;        //則讓j指向右孩子
 8        if(a[j] < a[j / 2])//如果左右孩子中較大的那個(gè)小于雙親，本次
 9            break;    //篩選結(jié)束
10        int t = a[j];
11        a[j] = a[j / 2];
12        a[j / 2] = t;
13    } 
14}

上面的算法還可以改進(jìn)，以減少交換次數(shù)：

 1void f(int *a, int top, int r)
 2{
 3    int j;
 4    int  t = a[top];
 5    int top1 = top;
 6    for(j = 2 * top; j <= r; j *= 2)
 7    {
 8        if(j < r && a[j] < a[j + 1]) 
 9            j++;
10        if(a[j] < t)
11            break;
12        a[top1] = a[j];
13        top1 = j;
14    } 
15    a[top1] = t;
16}