堆排序

从1开始计才保证左孩子是2i
 1 /*堆因为应用于排序，所以一般用数组存
 2 
 3 堆其实就是完全二叉树，可以直接从N/2开始调整（因为从大于它都没有孩子）(1开头的话才是左孩子是2i） 
 4 
 5 其实建堆和排序时的调整堆都是向下调整的，只不过建堆还要从N/2一直到1外层遍历一下 
 6 */ 
 7 #include<stdio.h>
 8 #include<malloc.h>
 9 void shift_down(int a[], int low, int high)
10 {
11     int i = low, j = 2*i;
12     int tmp = a[i];
13     while(j <= high){
14         if(j < high&&a[j] < a[j+1]){//要保证j+1<high 
15             j++;
16         } 
17         if(tmp < a[j]){
18             a[i] = a[j];
19             i = j;//迭代前的换位
20             j = 2*i;
21         } 
22         else break;//没动，就不用再往下了 
23     }
24     a[i] = tmp;//在上面j已经换成i了，最开始动的那个点一直攥在手上最后才落下 
25 }
26 void HeapSort(int a[], int n)
27 {
28     int tmp, i;
29     for(i = n; i >= 1; i--){
30         tmp = a[i];
31         a[i] = a[1];
32         a[1] = tmp;
33         shift_down(a, 1, i-1);//这里是i-1,不是i
34     }
35 }
36 int main()
37 {
38     int a[110], n, i;
39     scanf("%d", &n);
40     for(i = 1; i <= n; i++){
41         scanf("%d", &a[i]); 
42     } 
43     for(i = n/2; i >= 1; i--){
44         shift_down(a, i, n);
45     }
46     
47     HeapSort(a, n); 
48     for(i = 1; i <= n; i++){
49         printf("%d ", a[i]); 
50     }
51     return 0;
52 } 
53 /*10
54 6 8 7 9 0 1 3 2 4 5 */