堆排序（原理和C语言实现）

 1 void up2down(int *arr, int index, int end)
 2 {
 3     int index_child=(index<<1)+1;
 4     int key=arr[index];
 5     while(index_child<=end){
 6         if(index_child+1<=end&&\
 7 arr[index_child+1]>arr[index_child]){
 8             index_child++;
 9         }
10         if(arr[index_child]<=key){
11             break;
12         }
13         //这里和快排类似，不采用两两交换的算法
14         arr[index]=arr[index_child];
15         index=index_child;
16         index_child=(index_child)>>1+1;
17     }
18     arr[index]=key;
19 }
20 
21 void heap_sort(int *arr, int arr_len)
22 {
23     int index;
24     int temp;
25     //从最后一个非叶子结点向上遍历
26     for(index=(arr_len-1-1)>>1;index>=0;index--){
27         up2down(arr, index, arr_len-1);
28     }
29     for(index=arr_len-1;index>=1;index--){
30         temp=arr[0];
31         arr[0]=arr[index];
32         arr[index]=temp;
33         up2down(arr, 0, index-1)
34     }