堆排序是一種比較常用的排序方式，具有O(NlogN)的時間復雜度，它只需要一個記錄大小的空間，算法的核心是“篩選”。
堆的存儲方式是一維數組，因為它是一棵完全二叉樹，孩子與雙親下標有簡單直接的計算方式（數組下標從１開始）：節點i的左孩子下標為2 * i，右孩子下標為2 * i + 1，雙親節點下標為i / 2
堆排序的過程可分為兩步：
1.建立堆（經過n / 2次“篩選”，n為節點總個數）
2.不斷讓堆頂元素與堆的最后一個未排序的元素交換，并進行“篩選”，以維持堆的性質（該過程進行n - 1次后排序完成）。
下面我們以int型數組為例，通過建立大頂堆將數組a[]中的元素按升序排序。以下是算法代碼，其中f()是篩選函數，完成一次篩選。
1
int 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--)//從最后一個非葉子節點開始，建立大頂堆
7 {
8 f(a, i, n);
9
}
10 for(i = n; i > 1; i--)//經過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
}以下是不同版本的篩選函數f()
void f(int *a, int top, int r)
a為待排序數組，
top是堆頂
r是堆的最后一個元素
第一個是我寫的，很原始：
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}第二個是書上的，很簡潔：
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])//如果左右孩子中較大的那個小于雙親，本次
9 break; //篩選結束
10 int t = a[j];
11 a[j] = a[j / 2];
12 a[j / 2] = t;
13 }
14}上面的算法還可以改進，以減少交換次數：
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}
posted on 2012-07-16 11:18
小鼠標 閱讀(1170)
評論(0) 編輯 收藏 引用 所屬分類:
排序