快速排序：在當(dāng)前無序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個(gè)較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?br>復(fù)雜度：期望時(shí)間 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}