频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
排序算法之基数排序,随机数的产生和程序运行时间的计算
2011-10-06 16:03:39      个评论      
收藏   我要投稿

一,基数排序

基本思想:

 

按最低位优先法先对低位关键字进行排序,直到对最高位关键字排序为止,经过若干次分配和收集来实现排序

基数排序中用到了箱排序,每个箱子都是先进先出,因此采用队列是最合理的数据结构。如下图:

 \

 

开始采用顺序表的存储结构,每次分派10个Length长的队列,写了很多代码,运行却发现速度很慢,不符合基数排序的理论时间复杂度O(k*n),而且消耗内存也很多(10*n).找了原因可能是自己写的队列影响了速度,因此采用了以数组做存储结构,只分配n的长度,设一个计数标志数组记录存储位置。

 

 \

二,随机数产生

 

首先调用srand((int)time(NULL))函数,设定随机数种子。返回的随机数(确切地说是伪随机数)实际上都是根据递推公式计算的一组数值,当序列足够长,这组数值近似满足均匀分布。先调用srand初始化,一般用当前日历时间初始化随机数种子,这样每次执行代码都可以产生不同的随机数。

函数rand()可以生成0—RAND_MAX()之间的一个随机数,其中RAND_MAX 是stdlib.h 中定义的一个整数,它与系统有关。测试系统值RAND_MAX为32767,可以编写自己的库函数更改,由于本系统重在序列个数多少,和整数大小范围关系不大,因此没有在系统中实现。

本系统编写了一个随机产生low和high之间的整数:int RandomInteger(int low,int high)

其中产生low和high之间的函数语句:k=(long)(rand()%(high-low+1)+low);

 

三,时间函数

        clock_t start, finish; 

double duration; 

 

  start = clock();
radixsort(L,10000);
finish = clock(); 
duration = (double)(finish - start) / CLOCKS_PER_SEC;  

——————————————

 

代码分界线———————————————————————————

 

 

 

#include<stdio.h> 

#include<malloc.h> 

#include <stdlib.h> 

#include<time.h> 

//辅助函数,求数据的最大位数 

int maxbit(int L[],int n)  {  

  int d = 1,i=0; //保存最大的位数 

  int p=10; 

    for(i = 0;i < n; i++) { 

    while(L[i] >= p) { 

      p *= 10; 

      d++; 

    } 

  } 

  return d; 

//基数排序 

void radixsort(int L[],int len)  {  

  int d = maxbit(L,len);  

  long * tmp  = (long *)malloc(len*sizeof(long)); 

  long * count  = (long *)malloc(10*sizeof(long));; //计数器,10个桶  

  long i,j,k; 

  int radix = 1; 

  for(i = 1; i <= d; i++)  

  {  //进行d次排序     

    for(j = 0; j < 10;j++) //每次分配前清空计数器 

        count[j] = 0;  

    for(j = 0;j < len; j++)  

    { //统计每个桶中的记录数 

        k = (L[j]/radix)%10;  

        count[k]++; 

    } 

    for(j = 1;j < 10; j++) //将tmp中的位置依次分配给每个桶  

      count[j] = count[j-1] + count[j]; 

    for(j = len-1;j >= 0;j--)  

    { //将所有桶中记录依次收集到tmp中 

        k = (L[j]/radix)%10; 

        count[k]--; 

        tmp[count[k]] = L[j]; 

    } 

    for(j = 0;j < len;j++) //将临时数组的内容复制到L中 

        L[j] = tmp[j]; 

    radix = radix*10; 

  }  

  free(tmp); 

  free(count); 

}  

int RandomInteger(long low,long high) 

    long k; 

    k=(long)(rand()%(high-low+1)+low); 

    return k;  

}  

int main() 

    long i=0; 

    long * L  = (long *)malloc(10000*sizeof(long)); 

    clock_t start, finish;  

    double duration;  

     

        srand( (long)time( NULL ) );  

        for(i=0;i<10000;i++) 

        { 

            L[i]=i;//RandomInteger(0,10000); 

        } 

     

     

    start = clock(); 

    radixsort(L,10000); 

    finish = clock();  

    duration = (double)(finish - start) / CLOCKS_PER_SEC;   

    for(i=0;i<10000;i++) 

    { 

        printf("%7.2ld   ",L[i]); 

    } 

    printf("%5.4lfs  ",duration); 

    getchar(); 

    getchar();                            

    getchar(); 

    return 0; 

}   

 


 

 

creat by 张飞雪

点击复制链接 与好友分享!回本站首页
上一篇:排序算法之堆排序
下一篇:排序算法之快速排序
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站