algorithm/sortAlgorithm/heapSort.c at master · wait0804/algorithm · GitHub

Repository navigation

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

#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);

}