快速排序

基本思想：选择一个基准元素，通过一趟排序将待排的记录分割成两个独立的部分，其中一部分记录的值均比基准元素小，另一部分均比基准元素值大。然后分别对这两部分用同样的方法进行排序。

代码如下：

 1 void Qsort(int a[],int low,int high)
 2 {
 3     if(low<high)
 4     {
 5         int mid=Partition(a,low,high);
 6         Qsort(a,low,mid-1);//对低子表进行递归排序
 7         Qsort(a,mid+1,high);//对高子表进行递归排序
 8     }
 9 }
10 
11 
12 int Partition(int a[],int low,int high)
13 {
14     a[0]=a[low];//用子表的第一个记录作枢纽轴的记录
15     int key=a[low];//枢纽记录关键字
16     while(low<high)//从表的两端交替的向中间扫描
17     {
18         while(low<high&&a[low]<=key) ++low;
19         a[high]=a[low];//将比枢纽记录大的记录移动到高端
20         while(low<high&&a[high]>=key)--high;
21         a[low]=a[high];//将比枢纽记录小的记录移动到低端
22     }
23     a[low]=a[0];//枢纽记录到位
24     return low; //返回枢纽位置
25 }

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。