快速排序

快速排序算法是我们用的最佳的排序算法，虽然它的最坏时间为O（n2），但是它平均性能较好，期望运行时间O（nlgn）。另外它能够进行原地排序。

 1 #include<Stdio.h>
 2 int partition(int a[],int p,int r);
 3 void qSort(int a[],int p,int r);
 4 
 5 int main()
 6 {
 7     int a[9]={9,5,6,8,2,4,3,1,7};
 8     qSort(a,0,8);
 9     for(int i=0;i<9;i++)
10     {
11         printf("%d ",a[i]);
12     }
13     return 0;
14 }
15 void qSort(int a[],int p,int r)
16 {
17     if(p<r)
18     {
19         int q=partition(a,p,r);
20         qSort(a,p,q-1);
21         qSort(a,q+1,r);
22     }
23 }
24 int partition(int a[],int p,int r)
25 {
26     int i = p;
27     int j = r;
28     int x=a[r];
29     if(p<r)
30     {
31         while(i<j)
32         {
33             while(i<j&&a[i]<x)
34                 i++;
35             if(i<j)
36             {
37                 a[j]=a[i];
38                 j=j-1;
39             }
40             while(i<j&&a[j]>x)
41                 j--;
42             if(i<j)
43             {
44                 a[i]=a[j];
45                 i=i+1;
46             }
47         }
48     
49     }
50     a[i]=x;
51     return i;
52 }