//------------------------------------------------
//　这是自编排序代码 sorting 堪与 Shell 排序媲美
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>

typedef int  Type;
#define NMAX 10000000
Type stack[NMAX];

#define SWAP(a,b) {Type t=a;a=b;b=t;}

void sorting(Type A[ ],int num)
{
     if(num==2)
  {
        if(A[0]<A[1])SWAP(A[0],A[1]);
  }
     else if(num==3)
  {
        if(A[0]<A[1])SWAP(A[0],A[1]);
        if(A[1]<A[2])SWAP(A[1],A[2]);
        if(A[0]<A[1])SWAP(A[0],A[1]);
  }
     else
     {
        Type *p=stack,*boy,*girl;
        int N1,N2,i,j;
        N1 = num/2;
        N2 = num - N1;
        boy=A+0;
        girl=A+N1;
        sorting(boy ,N1); //递归
        sorting(girl,N2); //递归
        i=0;
        if(boy[0]<girl[0])goto here;
        do
        {
           for(i=1;i<N1;i++)if(boy[i]<girl[0])break;
           memcpy(p,boy,i*sizeof(Type));
           p+=i;boy+=i;N1-=i;
           if(N1)goto here;
           memcpy(p,girl,N2*sizeof(Type));
           p+=N2;girl+=N2;N2=0;
           goto outw;
        here:
           for(j=1;j<N2;j++)if(girl[j]<boy[0])break;
           memcpy(p,girl,j*sizeof(Type));
           p+=j;girl+=j;N2-=j;
        }
        while(N2>0);
        memcpy(p,boy,N1*sizeof(Type));
        p+=N1;boy+=N1;N1=0;
        outw:
        memcpy(A,stack,num*sizeof(Type));
     }
}

void Shell(Type *ary,int num) //希尓排序
{
     int i,j,dx=1;
     for(dx=(int)(num/2.7); dx>=1; dx=(int)(dx/2.7))
     for(i=dx; i<num; i++)
     {   Type t=ary[i];
         for(j=i; j>=dx && t>ary[j-dx]; j-=dx)
             ary[j]=ary[j-dx];
         ary[j]=t;
     }
}

int main( void )
{
    int i,t1,t2;
    static Type ary[NMAX];
    while(1)
    {
       printf("Random Seed: ");
       scanf("%d",&i);srand(i);
       for(i=0;i<NMAX;i++)
       ary[i]=rand( )％900+100;

       t1=clock( );
       sorting( ary,NMAX );//俺的排序
       //Shell( ary,NMAX );//希尓排序
       t2=clock( );

       for(i=0;i<NMAX;i+=100)printf("%d ",ary[i]);
       printf("\n%d ms\n",(t2-t1));
    }
    return 0;
}


      

收到的鲜花

• 遮天云 于 2010-12-10 22:36 送鲜花  50朵  
• BlueGuy 于 2010-12-11 08:35 送鲜花  -5朵  
• BlueGuy 于 2010-12-11 08:35 送鲜花  -5朵  
• BlueGuy 于 2010-12-11 08:35 送鲜花  -5朵  
• BlueGuy 于 2010-12-11 08:36 送鲜花  45朵  

为了考察排序速度的快慢，我用希尓排序函数与我自己写的代码进行比较。
从大到小对 1000万 个随机数（大小介于100～999之间）进行排序。
在我的机子上，希尓排序耗时 1.86 秒、俺的排序耗时 2.45 秒。
“用空间（内存）换时间（速度）”是我所编的排序代码的最大特点（也是缺点）。
具体说，为了给1000万个整型数排序，需要开销一个同样大小的stack[ ]数组。呜呼！
顺便指出，希尓排序代码中那个“2.7”是很关键的，如果换成“2”速度一下就慢了。

1楼代码的主体思路是基于“递归”：
为若干（num）个元素排序，首先归结为 N1 个“男生组”和 N2 个“女生组”的排序。式中 N1=num/2; N2=num-N1。
接下来的想法是，如果“男生组个子最高的boy[0]比女生组最高的girl[0]还高”则因组内已经排序，所以通过
搜索，确认从boy[0]到boy[i-1]都比girl[0]高大，换言之，从boy[0]到boy[i-1]已是“龙头老大”所以我们把
它们统统复制到stack[ ]中去。接着，搜索女生组，确认从girl[0]到girl[j-1]都比boy[i]高大，再把这些
“大个女孩”复制到stack[ ]中去（当然是排在那几个“龙头老大”之后啰）。至此，“男一号”已经变成
boy[i]、女一号已经变成girl[j]。为了让代码重复使用，必须刷新“指针”即 boy=boy+i; girl=girl+j;
两个组的人数也要修改：N1=N1-i; N2=N2-j; 至于对 stack[ ]进行“写”操作的指针 p 更是要不断更新。
 

看来看去，恕我直言，就觉得是一个写糟了的归并排序
因为思想和归并排序一模一样，但细节上处理的却不够原算法好