堆排序

 1 #include <stdio.h>
 2 #include <malloc.h>
 3 
 4 #define LeftChild(i) (2*(i)+1)
 5 
 6 typedef int ElementType;
 7 
 8 void SwapTwoNum(ElementType *Num_1,ElementType *Num_2)
 9 {
10     int NumTemp = *Num_1;
11     *Num_1 = *Num_2;
12     *Num_2 = NumTemp;
13 }
14 
15 void _PercDown(ElementType *Array,int CurrentPosition,int ArrayLen)
16 {
17     int Child;
18     ElementType TmpNum;
19     
20     for(TmpNum = Array[CurrentPosition];LeftChild(CurrentPosition) < ArrayLen;CurrentPosition = Child)
21     {
22         Child = LeftChild(CurrentPosition);
23         if(Child != ArrayLen-1 && Array[Child+1] > Array[Child])
24         {
25             Child ++;
26         }
27         if(TmpNum < Array[Child])
28         {
29             Array[CurrentPosition] = Array[Child];
30         }
31         else
32         {
33              break;
34         }
35     }
36     Array[CurrentPosition] = TmpNum;
37 }
38 
39 void HeapSort(ElementType *Array,int ArrayLen)
40 {
41     int i;
42     //Build Heap
43     for(i = ArrayLen/2;i >= 0;i --)
44     {
45         _PercDown(Array,i,ArrayLen);
46     }
47     
48     //Delete max and put them to the Array end
49     for(i = ArrayLen-1;i > 0;i --)
50     {
51         SwapTwoNum(&Array[0],&Array[i]);
52         _PercDown(Array,0,i);
53     }
54 }
55 
56 int main()
57 {
58     ElementType TestArray[10] = {718,224,3332,4443,55,31,66,79,90,7};
59     HeapSort(TestArray,10);
60     int i;
61     for(i = 0;i < 10;i ++)
62     {
63         printf("%d ",TestArray[i]);
64     }
65     printf("
");
66     return 0;
67 }