JUST DO IT

快速排序（windows+VC6.0环境编译）

快速排序：在当前无序区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}

posted on 2009-07-20 23:51 xmoss 阅读(542) 评论(0)  编辑 收藏 引用 所属分类: 结构和算法