Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4252722
  • 博文数量: 291
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 7924
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-06 14:28
个人简介

阿里巴巴是个快乐的青年

文章分类

全部博文(291)

文章存档

2018年(21)

2017年(4)

2016年(5)

2015年(17)

2014年(68)

2013年(174)

2012年(2)

分类: 架构设计与优化

2013-05-01 21:51:35

一、数据结构
        约定排序均为升序排序,要排序的记录存储在线性表中,线性表由排序关键字和其它域组成,其定义如下:
        struct element
        {
            int key[d];            // d为关键字的位数
            int next;    
        };
        element rsqlist[n];
      
二、算法思想
        基数排序的思想类似于扑克牌排队的方法。一般地,记录r[i]的关键字为r[i].key,r[i].key是由d位数字组成,即k1ik2i^kdi,每一个数字表示关键字的一位,其中k1为最高位,kd是最低位,每一位的值都在0<=ki
三、程序实现
        实现基数排序的函数如下:
        void radixsort(rsqlist r, int p, int d, int n)        // 排序元素r[1]~r[n]      
        {
            int f[rd], e[rd];                                     // 队的头、尾指示器,rd是基数,二进制数rd为2,十进制数rd为10
            for (k=1; k<=n-1; k++)
            {
                r[k].next = k + 1;
            }  
            r[n].next = 0;
            p = 1;                                                 // 原始数据串成静态链表,头指针为p
            for (i=d; i>0; i--)                                   // 从最后一位关键字开始
            {
                for (j=0; j                 {
                    f[j] = 0;                                      // 对指示器初值
                }
                while (0 != p)
                {
                    k = r[p].key[i];                            // 找到对号为k
                    if (0 == f[k])
                    {
                        f[k] = p;
                    }
                    else
                    {
                        r[e[k]].next = p;
                    }
                    e[k] = p;
                    p = r[p].next;                             // 进行分配
                }
                j = 0;
                while (0 == f[j])
                {
                    j++;                                          // 寻找第一个非空队
                }
                p = f[j];
                t = e[j];
                while (j < rd-1)
                {
                    j++;
                    if (0 != f[j])
                    {
                        r[t].next = f[j];
                        t = e[j];
                    }                                               // 进行收集
                    r[t].next = 0;                             // 收尾
                }
            }
        }
        基数排序算法的时间复杂度是O(d*(rd+n)),其中rd是基数,d为关键字的位数,n是元素个数,它是一种稳定的排序方法。




阅读(2911) | 评论(1) | 转发(3) |
给主人留下些什么吧!~~

scq2099yt2013-05-01 21:52:09

文明上网,理性发言...

评论热议
请登录后评论。

登录 注册