排序算法 堆排序

什么是堆排序？

堆排序就是利用堆这种数据结构，实现对数据的排序，是一种选择排序算法

什么是堆？

堆是一颗完全二叉数，有大根堆和小根堆之分，大根堆满足非叶子节点不小于子节点，所以大根堆根节点是最大值；小根堆满足非叶子节点不大于子节点，所以小根堆根节点是最小值。

如何利用堆对数据排序？

这里说明利用大根堆对数据进行排序的方法。

1. 将输入数据 data[0:n] 调整为大根堆
2. 将大根堆的根拿掉，和最后一个数据调换，n = n-1, 将数据 data[0:n] 调整为大根堆。
3. 循环执行步骤 2 ,直到 n=1。

运行结束后，最终得到的 data[0:n] 就是非递减的有序数据。

下面是示例代码：

#include 
/*
功能：大根堆调整，具体操作是将 data[s] 插入到大根堆 data[s+1:m]中。 
data 中的数据，除了data[s],后面的已经是大根堆了。
*/
void HeapAdjust(int data[],int s,int m)
{
    int tmp,j;
    tmp = data[s]; //将 data[s] 的值存起来
    for(j = 2*s+1;j <= m;j=j*2+1)// j 是 s 的左子节点
    {
        if( j < m && data[j] < data[j+1])++j; // 选出大的子节点
        if(tmp >= data[j])break;              // 不小于两个子节点，退出循环 
        data[s] = data[j]; s = j;             // 将大的子节点挪到 s 的位置，s 记录 tmp 要存放的位置 j
    }
    data[s] = tmp;                           // 将 tmp 放到合适的位置 
}

void HeapSort(int data[],int n)
{
    int i;
    int tmp;
    for(i = n/2-1;i>=0;--i)        // 将数据调整为大根堆
    {
        HeapAdjust(data,i,n-1);
    }
    for(i=n-1;i>0;--i)            // 开始排序
    {
        tmp = data[0];           
        data[0] = data[i];
        data[i] = tmp;           // 取出最大值与最后一个数据交换
        HeapAdjust(data,0,i-1);  // 找出剩下数据的最大值
    }
}
int main()
{
	int data[] = {54,59,39,9,79,64,16,6,76};
	int n = sizeof(data)/sizeof(data[0]);
    HeapSort(data,n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

应用

优先队列

值得一看：
堆排序算法
堆排序动画