快速排序：在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
复杂度：期望时间 O(n log n) , 最坏情况O(n2)
1
#include <stdio.h>
2#include <cstdlib>
3
4#define TOTAL_NUM 10
5#define MAX_NUM 100
6
7int quick(int sort[],int iLit,int iHig)
8
{
9
int ival = sort[iLit];
10 while (iLit<iHig)
11
{
12 while(iLit<iHig&&sort[iHig]>ival)iHig--;
13 sort[iLit] = sort[iHig];
14
15 while(iLit<iHig&&sort[iLit]<ival)iLit++;
16 sort[iHig] = sort[iLit];
17
}
18 sort[iLit] = ival;
19 return iLit;
20
}
21
22void SORT(int sort[],int iLit,int iHig)
23{
24 int iMid = 0;
25 if (iLit<iHig)
26 {
27 iMid = quick(sort,iLit,iHig);
28 SORT(sort,iLit,iMid-1);
29 SORT(sort,iMid+1,iHig);
30 }
31}
32
33int main(int argc,char* argv[])
34{
35 int Sort[TOTAL_NUM];
36
37 int iPrintCount = 0;
38 int i = 0;
39 printf("::: old order ::: \n");
40 for (i=0;i<TOTAL_NUM;i++)
41 {
42 Sort[i] = (rand()+MAX_NUM)%MAX_NUM;
43 printf("%5ld ",Sort[i]);
44 if(++iPrintCount==10)
45 {
46 iPrintCount = 0;
47 printf("\n");
48 }
49 }
50
51 //quick sort
52 SORT(Sort,0,TOTAL_NUM-1);
53
54 iPrintCount = 0;
55 printf("\n::: new order ::: \n");
56 for (i=0;i<TOTAL_NUM;i++)
57 {
58 printf("%5ld ",Sort[i]);
59 if(++iPrintCount==10)
60 {
61 iPrintCount = 0;
62 printf("\n");
63 }
64 }
65
66 getchar();
67 return 0;
68}