结构排序 只循环3*N次

时间:2010-05-06 12:01:24  来源:第二电脑网  作者:第二电脑网

  第二电脑网导读:     /*虽然num_n的空间大小和数据大小有点关系,但是影响并不是很大?*/           /*所以这个方法也使用于大型排序*/#define MAX_N 256   /*如果数据最大值特别大的话,可以进行层次排序那样可能多循环一些次数*/int *jgsort(int num[],int len) /*结构排序*/{  int *sort_n,*num_n,*snum;  int i,j,l=0;   /*不同数据量定义不同的变...
  正文:

#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次"由第二电脑网原创提供,转载请注明:http://www.002pc.com/master/College/Language/VC/2010-05-06/13887.html


关键字:

关于《结构排序 只循环3*N次》文章的评论

站内搜索: 高级搜索

热门搜索: Windows style 系统 tr IP QQ CPU 安装 function 注册 if td