• 堆排序和快速排序一样，时间复杂度为Ο(N㏒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
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
     1 //第一种方法
     2 #include <stdio.h>
     3 
     4 int h[101]; //用来存放堆的数组
     5 int n; //用来存储堆中元素的个数，也就是堆的大小
     6 
     7 //交换函数，用来交换堆中的两个元素的值
     8 void swap(int x, int y) {
     9     int t;
    10     t = h[x];
    11     h[x] = h[y];
    12     h[y] = t;
    13 }
    14 
    15 //向下调整
    16 void siftdown(int i) { //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始开始向下调整
    17     int t, flag = 0; //flag用来标记是否需要继续向下调整
    18     //当i结点有儿子（其实是至少有左儿子）且需要继续调整时，循环
    19     while (i*2 <= n && flag == 0) {
    20         //首先判断它和左儿子的关系，并用t记录较小的结点编号
    21         if (h[i] > h[i*2])
    22             t = i*2;
    23         else
    24             t = i;
    25         //如果它有右儿子，再对右儿子进行讨论
    26         if (i*2+1 <= n) {
    27             //如果右儿子的值更小，更新较小的结点编号
    28             if (h[t] > h[i*2+1])
    29                 t = i*2+1;
    30         }
    31         //如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
    32         if (t != i) {
    33             swap(t, i); //交换它们
    34             i = t; //更新i为刚才与它交换的二子结点的编号，便于接下来继续向下调整
    35         } else
    36             flag = 1; //否则说明当前的父结点已经比两个子结点都小，不需要进行调整
    37     }
    38 }
    39 
    40 //建立堆的函数
    41 void creat() {
    42     int i;
    43     //从最后一个非叶节点到第1个结点依次进行向上调整
    44     for (i = n/2; i >= 1; i--) {
    45         siftdown(i);
    46     }
    47 }
    48 
    49 //删除最大的元素
    50 int deletemax() {
    51     int t;
    52     t = h[1]; //用一个临时变量记录堆顶点的值
    53     h[1] = h[n]; //将堆的最后一个点赋值到堆顶
    54     n--; //堆的元素减少1
    55     siftdown(1); //向下调整
    56     return t; //返回之前记录的堆的顶点的最大值
    57 }
    58 
    59 int main() {
    60     int i, num;
    61     //读入要排序的数字的个数
    62     scanf("%d", &num);
    63 
    64     for (i = 1; i <= num; i++)
    65         scanf("%d", &h[i]);
    66     n = num;
    67 
    68     //建堆
    69     creat();
    70 
    71     //删除顶部元素，连续删除n次，其实也就是从大到小把数输出出来
    72     for (i = 1; i <= num; i++)
    73         printf("%d ", deletemax());
    74 
    75     return 0;
    76 }

  • 堆排序还有一种更好的方法：同样是升序排序，建立最大堆。建立后最大的元素在h[1]，因为我们希望最大的放在最后，因此我们将h[1]和h[n]交换，此时h[n]就是数组中最大的元素。请注意，交换后还需将h[1]向下调整以保持堆的特性。现在最大的元素已经归位，需要n–，然后再将h[1]和h[n]交换，将h[1]向下调整。如此反复，直到堆的大小为1。此时数组h中的数就排序好了。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 1 //第二种方法
 2 #include <stdio.h>
 3 
 4 int h[101]; //用来存放堆的数组
 5 int n; //用来存储堆中元素的个数，也就是堆的大小
 6 
 7 //交换堆中两个元素的值
 8 void swap(int x, int y) {
 9     int t;
10     t = h[x];
11     h[x] = h[y];
12     h[y] = t;
13 }
14 
15 //向下调整函数
16 void siftdown(int i) { //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
17     int t, flag = 0; //flag是用来标记是否需要继续向下调整
18     //当i结点有儿子（其实是至少有左儿子）且需要继续调整时，循环
19     while (i*2 <= n && flag == 0) {
20         //首先判断它和左儿子的关系，并用t记录值较大的结点编号
21         if (h[i] < h[i*2])
22             t = i*2;
23         else
24             t = i;
25         //如果它有右儿子，再对右儿子进行讨论
26         if (i*2+1 <= n) {
27             //如果右儿子的值更大，更新较小的结点编号
28             if (h[t] < h[i*2+1])
29                 t = i*2+1;
30         }
31         //如果发现最大的结点编号不是自己，说明子结点中有比父结点更大的
32         if (t != i) {
33             swap(t, i); //交换它们
34             i = t; //更新i为刚才与它交换的子结点的编号，便于接下来继续向下调整
35         } else
36             flag = 1; //否则说明当前的父结点已经比两个子结点都要大了，不需要再进行调整了
37     }
38 }
39 
40 //建立堆
41 void creat() {
42     int i;
43     //从最后一个非叶节点到第1个结点依次进行向上调整
44     for (i = n/2; i >= 1; i--) {
45         siftdown(i);
46     }
47 }
48 
49 //堆排序
50 void heapsort() {
51     while (n > 1) {
52         swap(1, n);
53         n--;
54         siftdown(1);
55     }
56 }
57 
58 int main() {
59     int i, num;
60     //读入n个数
61     scanf("%d", &num);
62 
63     for(i = 1; i <= num; i++)
64         scanf("%d", &h[i]);
65     n = num;
66 
67     //建堆
68     creat();
69 
70     //堆排序
71     heapsort();
72 
73     //输出
74     for (i = 1; i <= num; i++)
75         printf("%d ", h[i]);
76 
77     return 0;
78 }