深入解析Radix Sort基数排序算法思想及C语言实现示例

基本思想:

将待排数据中的每组关键字依次进行桶分配。
具体示例:

278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配,输出序列为:

505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配,输出序列为:

008、063、083、109、184、269、278、505、589、930

效率分析:

基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N>>M,因此额外空间需要大概N个左右。

但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,基数排序的应用范围更加广泛。

举例:
假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常,基数排序要用到计数排序或者桶排序。使用计数排序时,需要的是Order数组。使用桶排序时,可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
  int key[2];
};
struct linklist
{
  linklist *next;
  data value;
  linklist(data v,linklist *n):value(v),next(n){}
  ~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
  linklist *Bucket[101],*p;//建立桶
  int i,j,k,M;
  M=K/100+1;
  memset(Bucket,0,sizeof(Bucket));
  for (i=1;i<=N;i++)
  {
    k=A[i].key[y]/M; //把A中的每个元素按照的范围值放入对应桶中
    Bucket[k]=new linklist(A[i],Bucket[k]);
  }
  for (k=j=0;k<=100;k++)
  {
    for (p=Bucket[k];p;p=p->next) j++;
    for (p=Bucket[k],i=1;p;p=p->next,i++)
      A[j-i+1]=p->value; //把桶中每个元素取出
    delete Bucket[k];
  }
}
void RadixSort(data *A,int N,int K)
{
  for (int j=1;j>=0;j--) //从低优先到高优先 LSD
    BucketSort(A,N,K,j);
}
int main()
{
  int N=100,K=1000,i;
  data *A=new data[N+1];
  for (i=1;i<=N;i++)
  {
    A[i].key[0]=rand()%K+1;
    A[i].key[1]=rand()%K+1;
  }
  RadixSort(A,N,K);
  for (i=1;i<=N;i++)
    printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
  printf("\n");
  return 0;
}

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等。

对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。

(0)

相关推荐

  • 详解桶排序算法的思路及C++编程中的代码实现

    算法思路理解 我自己的理解哈,可能与网上说的有一些出入,大体都是同样的原理 无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等) 例如待排数字 [6 2 4 1 5 9] 准备10个空桶,最大数个空桶 [6 2 4 1 5 9] 待排数组 [0 0 0 0 0 0 0 0 0 0] 空桶 [0 1 2 3 4 5 6 7 8 9] 桶编号(实际不存在) 1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[

  • Objective-C实现冒泡排序算法的简单示例

    简介 冒泡算法是一种基础的排序算法,这种算法会重复的比较数组中相邻的两个元素.如果一个元素比另一个元素大(小),那么就交换这两个元素的位置.重复这一比较直至最后一个元素.这一比较会重复n-1趟,每一趟比较n-j次,j是已经排序好的元素个数.每一趟比较都能找出未排序元素中最大或者最小的那个数字.这就如同水泡从水底逐个飘到水面一样.冒泡排序是一种时间复杂度较高,效率较低的排序方法.其空间复杂度是O(n). 1, 最差时间复杂度 O(n^2) 2, 平均时间复杂度 O(n^2) 实现思路 1,每一趟比

  • JavaScript希尔排序、快速排序、归并排序算法

    以var a = [4,2,6,3,1,9,5,7,8,0];为例子. 1.希尔排序. 希尔排序是在插入排序上面做的升级.是先跟距离较远的进行比较的一些方法. function shellsort(arr){ var i,k,j,len=arr.length,gap = Math.ceil(len/2),temp; while(gap>0){ for (var k = 0; k < gap; k++) { var tagArr = []; tagArr.push(arr[k]) for (i

  • C/C++实现八大排序算法汇总

    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1. 插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已

  • 图文详解Heap Sort堆排序算法及JavaScript的代码实现

    1. 不得不说说二叉树 要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree).二叉树常被用于实现二叉查找树和二叉堆. 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒.二叉树的第 i 层至多有 2i - 1 个结点:深度为 k 的二叉树至多有 2k - 1 个结点:对任何一棵二叉树 T,如果

  • C语言选择排序算法及实例代码

    选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明 选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3  2  4  1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮 排序过程 (寻找第1小的数所在的位置) 3  2  4  1(最初, m

  • 简单掌握桶排序算法及C++版的代码实现

    桶排序介绍 桶排序(Bucket Sort)的原理很简单,它是将数组分到有限数量的桶子里. 假设待排序的数组a中共有N个整数,并且已知数组a中数据的范围[0, MAX).在桶排序时,创建容量为MAX的桶数组r,并将桶数组元素都初始化为0:将容量为MAX的桶数组中的每一个单元都看作一个"桶". 在排序时,逐个遍历数组a,将数组a的值,作为"桶数组r"的下标.当a中数据被读取时,就将桶的值加1.例如,读取到数组a[3]=5,则将r[5]的值+1. C++实现算法 假设数

  • 详解Bucket Sort桶排序算法及C++代码实现示例

    桶排序(Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里.每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序).桶排序是鸽巢排序的一种归纳结果.当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n)).但桶排序并不是比较排序,他不受到O(n log n)下限的影响. 桶排序以下列程序进行: 1.设置一个定量的数组当作空桶子. 2.寻访序列,并且把项目一个一个放到对应的桶子去. 3.对每个不是空的桶子进行排

  • 解读堆排序算法及用C++实现基于最大堆的堆排序示例

    1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

  • 桶排序算法的理解及C语言版代码示例

    理解: 桶排序是计数排序的变种,把计数排序中相邻的m个"小桶"放到一个"大桶"中,在分完桶后,对每个桶进行排序(一般用快排),然后合并成最后的结果. 基本思想: 桶排序假设序列由一个随机过程产生,该过程将元素均匀而独立地分布在区间[0,1)上.我们把区间[0,1)划分成n个相同大小的子区间,称为桶.将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. 效率分析: 桶排序的平均时间复杂度为线性的

随机推荐