快速排序
快速排序(以下简称快排)是一种排序算法，有C.A.R.Hoare所发展的，就如同他的名字一样，它的特点就是快。以平均效能来说，排序n个项目有O(n log n)次比较。在最差的效能下它需要O(n^2)次比较，所以它是一种不稳定排序法。
思路：
快排使用的分治(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。令其中一个子序列的元素小于另一个子序列，在对两个子序列采取同样递归操作。
(顺序排列)步骤为：
1.在数列中挑出一个元素作为"基准"(pivot)。
2.将比基准小的移到基准前面，比基准大的移到基准后面(相同的可以不必理会)。
3.递归(recursive)地对两个子序列排序。
C代码实现如下：
1 #include<stdio.h>
2 #define swap(x,y) {int t;t = x;x = y;y = t;} /*用于交换x和y的值*/
3
4 void quicksort(int *a,int left,int right)
5 {
6 int i=left,j=right+1,pivot=a[left]; /*以最左边的元素为“基准”*/
7 while(1)
8 {
9 while(++i<=right&&a[i]<pivot); /*从左边逐个找，直到找到比“基准”大的元素*/
10 while(--j>=left&&a[j]>pivot); /*从右边逐个找，直到找到比“基准”小的元素*/
11 if(i>=j) break;
12 swap(a[i],a[j]);
13 }
14 swap(a[j],a[left]); /*执行完上面的循环，j必定在i的位置活i的左边，且a[j]小于"基准"，所以交换a[j]和“基准”*/
15 if(left<j) quicksort(a,left,j); /*对“基准”左边排序*/
16 if(i<right) quicksort(a,i,right); /*对“基准”右边排序*/
17 }
18
19 int main()
20 {
21 int D[10]={9,8,7,6,5,4,3,2,1,0};
22 int i=0;
23 /* 输出排序前的数组 */
24 while(i<10)
25 printf("%d ",D[i++]);
26 putchar('\n');
27
28 quicksort(D,0,9);
29
30 i=0;
31 /* 输出排序后的数组 */
32 while(i<10)
33 printf("%d ",D[i++]);
34 putchar('\n');
35
36 return 0;
37 }
38
其实在C下对于快排可以直接使用qsort()(在stdlib.h有文件下),C++下可以使用sort()(在algorithm头文件下)。现在对C++的sort()掌握的还不是非常彻底，有机会再好好整理一下。