堆排序

本题要求实现堆排序中的筛选函数，待排序列的长度1<=n<=1000。

函数接口定义：

1 void HeapAdjust( HeapType  H, int s, int m);

其中L是待排序表，使排序后的数据从小到大排列。
###类型定义：

typedef  int  KeyType;
typedef  struct {                      
  KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
  int Length;      
}SqList;
typedef SqList HeapType; 

裁判测试程序样例：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef  int  KeyType;
 4 typedef  struct {                      
 5   KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
 6   int Length;      
 7 }SqList;
 8 typedef SqList HeapType; 
 9 void  CreatSqListHeapType *L);/*待排序列建立，由裁判实现，细节不表*/ 
10 void HeapAdjust( HeapType  H, int s, int m);
11 void HeapSort( HeapType  H);
12 int main()
13 {
14   HeapType L;
15   int i;
16   CreatSqList(&L);
17   HeapSort(L);
18   for(i=1;i<=L.Length;i++)
19    {        
20      printf("%d ",L.elem[i]);
21    }
22   return 0;
23 }
24 void HeapSort( HeapType  H)
25 { /*堆顺序表H进行堆排序*/
26   int i; KeyType rc;
27   /*建立初始堆*/
28   for( i=H.Length/2;i>0; i--)
29    {
30       HeapAdjust(H, i, H.Length);
31    }
32   for(i=H.Length;i>1;i--)
33    {
34       rc=H.elem[1];
35       H.elem[1]=H.elem[i]; 
36       H.elem[i]=rc;
37       HeapAdjust(H, 1, i-1); 
38    }
39  }
40 /*你的代码将被嵌在这里 */

代码如下:

void HeapAdjust( HeapType  H, int s, int m){
    int now=s;
    if(s*2<=m&&H.elem[s*2]>H.elem[now]){
        now<<=1;
    }
    if(s*2+1<=m&&H.elem[s*2+1]>H.elem[now]){
        now=s*2+1;
    }
    if(now!=s){
        int t=H.elem[s];
        H.elem[s]=H.elem[now];
        H.elem[now]=t;
        HeapAdjust(H,now,m);
    }
}