堆排序是一种比较常用的排序方式，具有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
小鼠标 阅读(1161)
评论(0) 编辑 收藏 引用 所属分类:
排序