#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这个内存空间
在外部排序时要多占用一个大型数据的硬盘空间
当然这些都是在排序过程中所占用的
希望高手专家帮我评判一下这个排序方法
