朱自清的春的概括:一步一步写算法（之堆排序）

一步一步写算法（之堆排序）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    堆排序是另外一种常用的递归排序。因为堆排序有着优秀的排序性能，所以在软件设计中也经常使用。堆排序有着属于自己的特殊性质，和二叉平衡树基本是一致的。打一个比方说，处于大堆中的每一个数据都必须满足这样一个特性：

    （1）每一个array[n] 大于array[2*n]

    （2）每一个array[n]大于array[2 * n + 1]

    构建这样一个堆只是基础，后面我们需要每次从堆的顶部拿掉一个数据，不断调整堆，直到这个数组变成有序数组为主。所以详细的堆排序算法应该是这样的：

    1）构建大堆，使得堆中的每一个数据都满足上面提到的性质

    2）将堆的第一个数据和堆的最后一个数据进行互换，然后重新调整堆，直到堆重新平衡为止

    3）重复2）的过程，直到整个数组有序。

    上面的描述过程很简单，那么实践操作是怎么样的呢？

    a）对入参进行判断

view plaincopy to clipboardprint?

1. void heap_sort(int array[], int length)  
2. {  
3.     if(NULL == array || 0 == length)  
4.         return ;  
5.   
6.     /* to make sure data starts at number 1 */  
7.     _heap_sort(array-1, length);  
8. }  

view plaincopy to clipboardprint?

1. void _heap_sort(int array[], int length)  
2. {  
3.     int index = 0;  
4.     int median = 0;  
5.     construct_big_heap(array, length);  
6.   
7.     for(index = length; index > 1; index --)  
8.     {  
9.         median = array[1];  
10.         array[1] = array[index];  
11.         array[index] = median;  
12.   
13.         reconstruct_heap(array, 1, index-1);  
14.     }  
15. }  

view plaincopy to clipboardprint?

1. void set_sorted_value(int array[], int length)  
2. {  
3.     int index = length;  
4.     int median = 0;  
5.     if(length == 1) return;  
6.   
7.     while(index > 1){  
8.         if(array[index >> 1] >= array[index])  
9.             break;  
10.   
11.         median = array[index];  
12.         array[index] = array[index >> 1];  
13.         array[index >> 1] = median;  
14.         index >>= 1;  
15.     }  
16. }  
17.   
18. void construct_big_heap(int array[], int length)  
19. {  
20.     int index = 0 ;  
21.   
22.     for(index = 1; index <= length; index ++)  
23.     {  
24.         set_sorted_value(array, index);  
25.     }  
26. }  

view plaincopy to clipboardprint?

1. void reconstruct_heap(int array[], int index, int length)  
2. {  
3.     int swap = 0;  
4.     if(length < index << 1)  
5.         return;  
6.   
7.     if(length == index << 1){  
8.         adjust_leaf_position(array, index);  
9.         return;  
10.     }  
11.   
12.     if(-1 != (swap = adjust_normal_position(array, index))){  
13.         reconstruct_heap(array, swap, length);  
14.     }  
15. }  

view plaincopy to clipboardprint?

1. int adjust_normal_position(int array[], int index)  
2. {  
3.     int left = index << 1 ;  
4.     int right = left + 1;  
5.     int median = 0;  
6.     int swap = 0;  
7.   
8.     if(array[index] >= array[left]){  
9.         if(array[index] >= array[right]){  
10.             return -1;  
11.         }else{  
12.             swap = right;  
13.         }  
14.     }else{  
15.         if(array[index] >= array[right]){  
16.             swap = left;  
17.         }else{  
18.             swap = array[left] > array[right] ? left : right;  
19.         }  
20.     }  
21.   
22.     if(swap == left) {  
23.         median = array[index];  
24.         array[index] = array[left];  
25.         array[left] = median;  
26.     }else{  
27.         median = array[index];  
28.         array[index] = array[right];  
29.         array[right] = median;  
30.     }  
31.   
32.     return swap;  
33. }  
34.   
35. STATUS adjust_leaf_position(int array[], int index)  
36. {  
37.     int median = 0;  
38.     if(array[index] > array[index << 1])  
39.         return TRUE;  
40.   
41.     median = array[index];  
42.     array[index] = array[index << 1];  
43.     array[index << 1] = median;  
44.     return FALSE;  
45. }  

view plaincopy to clipboardprint?

1. static void test1()  
2. {  
3.     int array[] = {1};  
4.     heap_sort(array, sizeof(array)/sizeof(int));  
5. }  
6.   
7. static void test2()  
8. {  
9.     int array[] = {2, 1};  
10.     heap_sort(array, sizeof(array)/sizeof(int));  
11.     assert(1 == array[0]);  
12.     assert(2 == array[1]);  
13. }  
14.   
15. static void test3()  
16. {  
17.     int array[] = {3, 2, 1};  
18.     heap_sort(array, sizeof(array)/sizeof(int));  
19.     assert(1 == array[0]);  
20.     assert(2 == array[1]);  
21.     assert(3 == array[2]);  
22. }  
23.   
24. static void test4()  
25. {  
26.     int array[] = {2, 3, 1};  
27.     heap_sort(array, sizeof(array)/sizeof(int));  
28.     assert(1 == array[0]);  
29.     assert(2 == array[1]);  
30.     assert(3 == array[2]);  
31. }  
32.   
33. static void test5()  
34. {  
35.     int array[] = {5,3, 4, 1};  
36.     heap_sort(array, sizeof(array)/sizeof(int));  
37.     assert(1 == array[0]);  
38.     assert(3 == array[1]);  
39.     assert(4 == array[2]);  
40.     assert(5 == array[3]);  
41. }  
42.   
43. static void test6()  
44. {  
45.     int array[] = {2, 3,6, 8, 7};  
46.     heap_sort(array, sizeof(array)/sizeof(int));  
47.     assert(2 == array[0]);  
48.     assert(3 == array[1]);  
49.     assert(6 == array[2]);  
50.     assert(7 == array[3]);  
51.     assert(8 == array[4]);  
52. }  
53.   
54. static void test7()  
55. {  
56.     int array[] = {3,4,2,7,1,9,8,6,5};  
57.     heap_sort(array, sizeof(array)/sizeof(int));  
58.     assert(1 == array[0]);  
59.     assert(2 == array[1]);  
60.     assert(3 == array[2]);  
61.     assert(4 == array[3]);  
62.     assert(5 == array[4]);  
63.     assert(6 == array[5]);  
64.     assert(7 == array[6]);  
65.     assert(8 == array[7]);  
66.     assert(9 == array[8]);  
67. }