排序算法之堆排序及其C语言代码实现

概述：堆排，实际上是一种选择排序，只不过采用了堆这种数据结构，利用这种数据结构，使得在每次查找最大元素时，直接选取堆顶元素，从而时间大大缩短，相对简单选择排序算法来说，比较高效。
堆排序算法可描述如下：
1.将待排元素依次存入数组，该数组即为一颗完全二叉树；
2.从最后一个非叶节点开始递减，逐次将每个相应的二叉树调整成最大堆，最后，整个二叉树即为最大堆；
3.交换堆顶元素与堆尾元素，调整新的堆为最大堆，数组分为两部分：堆与已排序列，直至最后一个堆元素。
从上面可以看出，堆排序大致可以分为三个步骤：
1.存入数据（完全二叉树）
2.将前n个元素调整为最大堆
3.交换堆顶和堆尾元素，n=n-1，转2
注：本文元素从数组下标1开始储存，所以parent访问二叉树左右儿子分别为2*parent 和 2*parent+1；
两个核心函数：

void HeapAdjust(int H[],int start,int end)//堆调整，将start和end之间的元素调整为最大堆
void HeapSort(int H[],int L,int R)//堆排序
1
2

核心代码实现：

void HeapAdjust(int H[],int start,int end)//堆调整，将start和end之间的元素调整为最大堆
{
    int temp=H[start];
    int parent=start,child;
    while(2*parent<=end)
    {
        child=2*parent;
        if(child!=end&&H[child]<H[child+1])++child;
        if(temp>H[child])break;
        else H[parent]=H[child];
        parent=child;
    }
    H[parent]=temp;
}
 
void HeapSort(int H[],int L,int R)
{
    for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
        HeapAdjust(H,i,R);
    for(int i=R;i>=L;--i)
    {
        swap(&H[L],&H[i]);
        HeapAdjust(H,L,i-1);
    }
}
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

测试样例：

#include <stdio.h>
#define NA -1
void swap(int *a,int *b)//该函数用于交换两个变量的值
{
    int temp=*a;
    *a=*b;
    *b=temp;
}
void HeapAdjust(int H[],int start,int end)//堆调整，将start和end之间的元素调整为最大堆
{
    int temp=H[start];
    int parent=start,child;
    while(2*parent<=end)
    {
        child=2*parent;
        if(child!=end&&H[child]<H[child+1])++child;
        if(temp>H[child])break;
        else H[parent]=H[child];
        parent=child;
    }
    H[parent]=temp;
}
void HeapSort(int H[],int L,int R)
{
    for(int i=(R-L+1)/2;i>=L;--i)//调整整个二叉树为最大堆
        HeapAdjust(H,i,R);
    for(int i=R;i>=L;--i)
    {
        swap(&H[L],&H[i]);
        HeapAdjust(H,L,i-1);
    }
}
 
int main(){
    int A[]={NA,1,3,63,5,78,9,12,52,8};//从1开始存入数据
    printf("Previous Arrary:");
    for(int i=1;i<=9;++i)
        printf(" %d",A[i]);
    HeapSort(A,1,9);
    printf("\nSorted Arrary:");
    for(int i=1;i<=9;++i)
        printf(" %d",A[i]);
    printf("\n");
    return 0;
}
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
41
42
43
44
45

运行结果：

Previous Arrary: 1 3 63 5 78 9 12 52 8
Sorted Arrary: 1 3 5 8 9 12 52 63 78
请按任意键继续. . .
1
2
3

另：推荐一篇比较详细的文章，读者可以参看堆排序 Heap Sort