快速排序

本题要求实现快速排序的一趟划分函数，待排序列的长度1<=n<=1000。

函数接口定义：

1 int Partition ( SqList L, int low,  int high )；

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

1 typedef  int  KeyType;
2 typedef  struct 
3 {                      
4   KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                       
5   int Length;      
6 }SqList;

裁判测试程序样例：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef  int  KeyType;
 4 typedef  struct 
 5 {                      
 6   KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/                     
 7   int Length;      
 8 }SqList;
 9 void  CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/ 
10 int Partition ( SqList  L,int low,  int  high );
11 void Qsort ( SqList  L,int low,  int  high );
12 int main()
13 {
14   SqList L;
15   int i;
16   CreatSqList(&L);
17   Qsort(L,1,L.Length);
18   for(i=1;i<=L.Length;i++)
19       printf("%d ",L.elem[i]);
20   return 0;
21 }
22 void Qsort ( SqList  L,int low,  int  high ) 
23 { 
24     int  pivotloc;
25     if(low<high)
26     {  
27         pivotloc = Partition(L, low, high ) ;
28         Qsort (L, low, pivotloc-1) ; 
29         Qsort (L, pivotloc+1, high );
30      }
31 }
32 /*你的代码将被嵌在这里 */

代码如下:

int Partition ( SqList  L,int low,  int  high ){
    L.elem[0]=L.elem[low];
    int l=low,r=high;
    while(l<r){
        while(r>l&&L.elem[r]>=L.elem[0]) r--;
        L.elem[l]=L.elem[r];
        while(l<r&&L.elem[l]<=L.elem[0]) l++;
        L.elem[r]=L.elem[l];
    }
    L.elem[l]=L.elem[0];
    return l;
}