-
Notifications
You must be signed in to change notification settings - Fork 4
/
6、heapSort.c
76 lines (62 loc) · 1.56 KB
/
6、heapSort.c
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
/*
堆排序,时间复杂度:O(nlogn)
*/
#include<stdio.h>
void heapSort(int *a, int count);
void siftDown(int *a, int count, int start);
void swap(int *a, int *b);
int removeHeap(int *a, int n);
int removeHeap(int *a, int n){
int key = a[0];
a[0] = a[n];
siftDown(a, n, 0);
return key;
}
void swap(int *a, int *b){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void siftDown(int *a, int count, int start){
int i = start;
int j = 2*i+1;
while(j < count){ // 说明有左子树
if(j < count-1 && a[j] > a[j+1]){ // 表示存在右孩子的情况下;
j++; // j:表示指向左右子树中最小的一个
}
if(a[i] <= a[j]){
break; // 不用调整,父节点的值是最小的;
}else{
swap(&a[i], &a[j]);
// 交换
i = j; // 一直往树下交换,一直调整到叶子结点
j = 2*i+1;
}
}
}
void heapSort(int *a, int count){
int curPos = count/2-1; // 最后一个非叶子结点
int i;
int key;
while(curPos >= 0){
siftDown(a, count, curPos);
curPos--;
}
/* 输出构建好的堆结构
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
*/
for(i = 0; i < count; i++){
key = removeHeap(a, count-i-1); // 传参:第二个参数是下标
printf("%d ", key);
}
printf("\n");
}
void main(void){
int a[] = {3, 5, 7, 1, 4, 2, 9, 10};
int count = sizeof(a)/sizeof(int);
heapSort(a, count);
}