结构排序只循环3*N次

原帖及讨论：http://bbs.bccn.net/thread-90562-1-1.html

#include "stdio.h"
#include "stdlib.h"
#include "time.h"

#define ML 200        /*数值比较小的时候属于内部排序*/
                      /*在大型数据里，进行外部排序的时候，由于sort_n占的空间由数据最大值决定*/
                      /*虽然num_n的空间大小和数据大小有点关系，但是影响并不是很大?*/
                      /*所以这个方法也使用于大型排序*/
#define MAX_N 256     /*如果数据最大值特别大的话，可以进行层次排序那样可能多循环一些次数*/

int *jgsort(int num[],int len) /*结构排序*/
{
    int *sort_n,*num_n,*snum;
    int i,j,l=0;     /*不同数据量定义不同的变量类型*/
    int ma;

    snum=(int *)malloc(len*sizeof(int));
    for(i=0;i<ML;i++)   /*如果你知道最大值可以省去这个N次循环*/
    {
        ma=ma>num[i]?ma:num[i];
    }

sort_n=(int *)calloc(ma+1,sizeof(int)); /*应用中最好加个空间判断*/
num_n=(int *)calloc(ma+1,sizeof(int));

    for(i=0;i<ML;i++)    /*进行结构储存*/
    {
        if(sort_n[num[i]])
            num_n[num[i]]++;
        else
            sort_n[num[i]]=i+1;
    }

    for(i=0;i<=ma;i++)     /*进行重组装*/
    {
        if(sort_n[i])
        {
            for(j=0;j<=num_n[i];j++)
            {
                snum[l]=num[sort_n[i]-1];
                l++;
            }
        }
    }

free(sort_n);
free(num_n);

return snum;
}

int sort(int num[],int len)    /*冒泡排序*/
{
    int l,i,j;

    for(i=0;i<len-1;i++)
     for(j=i;j<len;j++)
     {
         if(num[i]>num[j])
         {
            l=num[i];
            num[i]=num[j];
            num[j]=l;
         }
     }
}

void main()
{
int num[ML],*snum;
int i;

    srand((unsigned)time(NULL)); /*产生数据*/
    for(i=0;i<ML;i++)
    {
        num[i]=rand()%MAX_N;
        printf("%3d ",num[i]);
    }

snum=jgsort(num,ML);/*获得排序后的数据*/

    puts("");
    for(i=0;i<ML;i++)
    {
        printf("%3d ",snum[i]);
    }

sort(num,ML); /*用冒泡排序做个验证*/

    puts("");
    for(i=0;i<ML;i++)
    {
        printf("%3d ",num[i]);
    }
    getch();
}

很明显能看到这个排序的方法只循环了3*N次
而且中间的计算与控制操作占用的时间非常短

缺点:在内部排序时浪费了num这个内存空间
在外部排序时要多占用一个大型数据的硬盘空间
当然这些都是在排序过程中所占用的

希望高手专家帮我评判一下这个排序方法

结构排序 只循环3*N次

结构排序只循环3*N次