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
| #include <stdio.h>
#define ARRSIZE(arr) (sizeof(arr) / sizeof(arr[0]))
void Swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//将第i个节点的左子树(i*2)右子树(i*2+1)调整为最大堆
void AdjustHeap(int elements[], int i, int len)
{
//默认根结点为最大值
int max = i;
//若存在左节点且右节点的值大于根结点
if (i * 2 < len && elements[i] < elements[i * 2])
max = i * 2;
//若存在右节点且右节点的值大于根结点
if (i * 2 + 1 < len && elements[max] < elements[i * 2 + 1])
max = i * 2 + 1;
//将更大的值作为根结点
if (elements[i] < elements[max])
{
Swap(&elements[i], &elements[max]);
AdjustHeap(elements, max, len);
}
}
void HeapSort(int elements[], int len)
{
//构建最大堆
for (int i = len / 2; i >= 0; i--)
AdjustHeap(elements, i, len);
//每次将一个最大值堆顶与堆低(节点数减1)交换，节点数减1，直到只剩下堆顶则是序列是有序的。
for (int i = len - 1; i > 0; i--)
{
Swap(&elements[0], &elements[i]);
AdjustHeap(elements, 0, i);
}
}
int main(int argc, char const *argv[])
{
int elems[] = {3, 4, 2, 1, 5, 9, 2, 1, 0, 22, 33, 5, 112, 11, 22, 55, 22, 61, 97};
int len = ARRSIZE(elems);
HeapSort(elems, len);
for (int i = 0; i < len; i++)
printf("%4d", elems[i]);
printf("\n");
return 0;
}
|