c语言实现基数排序解析及代码示例

1.

基数排序（radixsort）属于“分配式排序”（distributionsort），又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

2.基数排序的实现方法分为两种：

最高位优先(MostSignificantDigitfirst)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(LeastSignificantDigitfirst)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

3.LSD基数排序的原理及代码实现如下：

第一步

假设原来有一串数值如下所示：

73,22,93,43,55,14,28,65,39,81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：

0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

81,22,73,93,43,14,55,65,28,39

接着再进行一次分配，这次是根据十位数来分配：

0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列：

14,22,28,39,43,55,65,73,81,93

这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; 

int getDigitNum(int x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    res ++;
    x /= 10;
  }
  return res;
}
void RadixSort(int data[], int n){
  //find the Maximum and its digit number
  int Max = data[0];
  for(int i = 1; i < n; i++){
    if(Max < data[i]) Max = data[i];
  }
  int maxNum = getDigitNum(Max);
  //maxNum times radix sort
  int divisor = 1;
  for(int k = 0; k < maxNum; k++){
    vector<int> g[10];//g[i]中包含了"末位"数字是i的data[]数组中的元素
    for(int i = 0; i < 10; i++) g[i].clear();
    for(int i = 0; i < n; i++){
      int tmp = data[i] / divisor % 10;
      g[tmp].push_back(data[i]);
    }
    int cnt = 0;
    for(int i = 0; i < 10; i++){
      for(int j = 0; j < g[i].size(); j++){
        data[cnt++] = g[i][j];
      }
    }
    divisor *= 10;
  }
}
int main(){
  int Array[10] = {73,22,93,43,55,14,28,65,39,81};
  RadixSort(Array, 10);
  for(int i = 0; i < 10; i++){
    printf("%d ", Array[i]);
  }
  printf("\n");
  return 0;
}

总结

以上就是本文关于c语言实现基数排序解析及代码示例的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • C语言数据结构之学生信息管理系统课程设计

    本文实例为大家分享了学生信息管理系统设计的具体代码,供大家参考,具体内容如下 建立一个动态链表,链表中每一结点包括:学号.姓名.性别.年龄.成绩.程序能实现以下功能: 建立链表      显示链表      查找链表中是否存在某个元素,并显示这个元素的所有信息,若没有这个元素则显示"无此记录!"的信息.      删除链表中指定学号的结点.      在链表中指定的位置插入一个新结点(学号不能和其他结点重复). 要求:程序运行中,先显示实现以上功能所构成的菜单,然后根据选项调用相应程序

  • c语言通过opencv实现轮廓处理与切割

    c语言通过opencv实现轮廓处理与切割

    注意在寻找轮廓时要选择中寻找外层轮廓 RETR_EXTERNAL #include "opencv/cv.h" #include "opencv/highgui.h" using namespace std; using namespace cv; int main() { Mat srcimg=imread("./22.jpg"); Mat dst; cvtColor(srcimg,dst,CV_BGR2GRAY); threshold(dst

  • 利用C语言玩转魔方阵实例教程

    利用C语言玩转魔方阵实例教程

    魔方阵 魔方阵,古代又称"纵横图",是指组成元素为自然数1.2-n的平方的n×n的方阵,其中每个元素值都不相等,且每行.每列以及主.副对角线上各n个元素之和都相等. 如3×3的魔方阵: 8 1 6 3 5 7 4 9 2 魔方阵的排列规律如下: (1)将1放在第一行中间一列: (2)从2开始直到n×n止各数依次按下列规则存放:每一个数存放的行比前一个数的行数减1,列数加1(例如上面的三阶魔方阵,5在4的上一行后一列): (3)如果上一个数的行数为1,则下一个数的行数为n(指最下一行);

  • C语言中输入函数(scanf()、fgets()和gets())的区别详解

    前言 大家都知道在C语言中,有三种主要的输入函数:scanf(),fgets()以及gets().他们的使用方法及注意事项如下: 1.scanf() 它是一种格式化的输入方式,可一次性按照规定的格式输入多个数据域. scanf函数是一个标准库函数,它的函数原型在头文件"stdio.h"中.与printf函数相同,C语言也允许在使用scanf函数之前不必包含stdio.h文件. scanf函数的一般形式为: scanf("格式控制字符串", 地址表列); 其中,格式控

  • C语言实现二叉树的基本操作

    二叉树是一种非常重要的数据结构.本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历.中序遍历.后序遍历.层次遍历),二叉搜索树的构造等. 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵空树,则将该节点作为根节点:否则按照从左到右.先左子树后右子树的顺序逐个添加节点.比如依次添加节点:1,6,10,2,7,11,则得到的二叉树为: 在这里,我们需要借助一个链表来保存节点,以实现二叉树的顺序插入,具体做法如下: 1.0 初始化一个用来保存二叉树节

  • 利用C语言实现“百马百担”问题方法示例

    利用C语言实现“百马百担”问题方法示例

    前言 百马百担问题,有100匹马,驮100担货,大马驮3担,中马驮2担,两匹小马驮1担,问共有多少种驮法?且各种驮法中大.中.小马各多少匹? [分析] 1.定义整型变量m.n.k分别存放大马匹数.中马匹数.小马匹数: 2.定义整型变量sum存放共有几种驮法,且sum赋初值为0: 3.根据题意,大马.中马.小马共100匹:大马.中马.小马驮100担货满足如下关系: m+n+k=100(匹) 3*m+2*n+1/2*k=100(担) 4.三个未知数,两个方程,此题有若干组解: 5.计算机求解此类问题

  • C语言创建动态dll和调用dll(visual studio 2013环境下)

    C语言创建动态dll和调用dll(visual studio 2013环境下)

    第一部分:创建动态dll库. 1.打开visual studio 创建一个控制台应用程序. 2.选择DLL,空项目. 3.点击源文件,创建一个main.c文件 4.在main.c中写入一个简单的函数,内容如下: __declspec(dllexport) int mymax(int a,int b){ return a + b; } 5.编译生成. 6.在项目的目录有dll和lib两个生成好的文件. 第二部分:在新建项目中使用dll. 7.新建一个c的控制台应用程序UseDll,把Dll.dll

  • C语言结构体定义的方法汇总

    什么是结构体? 在C语言中,结构体(struct)指的是一种数据结构,是C语言中聚合数据类型(aggregate data type)的一类.结构体可以被声明为变量.指针或数组等,用以实现较复杂的数据结构.结构体同时也是一些元素的集合,这些元素称为结构体的成员(member),且这些成员可以为不同的类型,成员一般用名字访问. 结构体与数组的比较 (1) 都由多个元素组成 (2) 各个元素在内存中的存储空间是连续的 (3) 数组中各个元素的数据类型相同,而结构体中的各个元素的数据类型可以不相同 结

  • c语言实现基数排序解析及代码示例

    1. 基数排序(radixsort)属于"分配式排序"(distributionsort),又称"桶子法"(bucketsort)或binsort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶"中,藉以达到排序的作用. 2.基数排序的实现方法分为两种: 最高位优先(MostSignificantDigitfirst)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码

  • Java语言字典序排序算法解析及代码示例

    字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的

  • java数据结构之树基本概念解析及代码示例

    java数据结构之树基本概念解析及代码示例

    Java中树的存储结构实现 一.树 树与线性表.栈.队列等线性结构不同,树是一...节点与节点之间的父子关系,可以为每个节点增加一个parent域,用以记录该节点的父点 树是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合.它是由n(n>0)个有限节点组成一个具有层次关系的集合.把 它叫做"树"是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 树定义和基本术语 定义 树(Tree)是n(n≥0)个结点的有限集T,并且当

  • java多线程编程同步器Future和FutureTask解析及代码示例

    publicinterfaceFuture<V>Future表示异步计算的结果.它提供了检查计算是否完成的方法,以等待计算的完成,并获取计算的结果.计算完成后只能使用get方法来获取结果,如有必要,计算完成前可以阻塞此方法.取消则由cancel方法来执行.还提供了其他方法,以确定任务是正常完成还是被取消了.一旦计算完成,就不能再取消计算.如果为了可取消性而使用Future但又不提供可用的结果,则可以声明Future<?>形式类型.并返回null作为底层任务的结果. Future主要

  • TreeSet判断重复元素解析及代码示例

    TreeSet的底层是TreeMap的keySet(),而TreeMap是基于红黑树实现的,红黑树是一种平衡二叉查找树,它能保证任何一个节点的左右子树的高度差不会超过较矮的那棵的一倍. TreeMap是按key排序的,所以TreeSet中的元素也是排好序的.显然元素在插入TreeSet时compareTo()方法要被调用,所以TreeSet中的元素要实现Comparable接口.TreeSet作为一种Set,它不允许出现重复元素.TreeSet是用compareTo()来判断重复元素的,而非eq

  • Python语言异常处理测试过程解析

    这篇文章主要介绍了Python语言异常处理测试过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 (一)异常处理 1.捕获所有异常 try: x = 5 / 0 except: print('程序有错误') 2.捕获特定异常 try: x = 5 / 0 except ZeroDivisionError as e: print('不能为0',e) except: print('其他错误') else: print('没有错误') final

  • Java编程实现邻接矩阵表示稠密图代码示例

    Java编程实现邻接矩阵表示稠密图代码示例

    我们知道,要表示结点,我们可以用一个一维数组来表示,然而对于结点和结点之间的关系,则无法简单地用一维数组来表示了,我们可以用二维数组来表示,也就是一个矩阵形式的表示方法. 我们假设A是这个二维数组,那么A中的一个元素aij不仅体现出了结点vi和结点vj的关系,而且aij的值正可以表示权值的大小. 邻接矩阵模型类 邻接矩阵模型类的类名为AMWGraph.java,能够通过该类构造一个邻接矩阵表示的图,且提供插入结点,插入边,取得某一结点的第一个邻接结点和下一个邻接结点. import java.u

  • GO语言实现文件上传的示例代码

    GO语言实现文件上传的示例代码

    目录 前言 文件上传 表单操作 服务端操作 流程实现 小结 前言 最近在写一个文件上传的功能,现在来进行整理总结一下go语言如何上传文件的,本文主要分享一下golang实现文件上传的流程和具体代码,供大家参考,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助. 文件上传 表单操作 要使表单能够上传文件,需要添加form的enctype属性enctype="multipart/form-data",upload.html代码如下: <html> <head> &

  • 利用Go语言实现流量回放工具的示例代码

    利用Go语言实现流量回放工具的示例代码

    目录 前言 goreplay介绍与安装 使用示例 流量放大.缩小 流量写入到ElastichSearch goreplay基本实现原理 总结 前言 哈喽,大家好,我是asong. 今天给大家推荐一款使用Go语言编写的流量回放工具 -- goreplay:工作中你一定遇到过需要在服务器上抓包的场景,有了这个工具就可以助你一臂之力,goreplay的功能十分强大,支持流量的放大.缩小,并且集成了ElasticSearch,将流量存入ES进行实时分析: 废话不多,我们接下来来看一看这个工具: gore

  • C语言实现扫雷小游戏的示例代码

    C语言实现扫雷小游戏的示例代码

    目录 一.扫雷 1.演示效果 2.完整代码 二.代码解析 1.初始化雷盘 2.打印雷盘 3.布置雷 4.排雷 5.游戏函数主体 6.菜单函数 7.头文件.宏定义及主函数 一.扫雷 扫雷小游戏主要是利用字符数组.循环语句和函数实现. 设计思路:雷盘大小为9*9,但是为了后续能更好的统计出雷的个数在定义数组的时候定义大小为11*11,先定义两个字符数组,一个用来记录雷的位置,另一个用来展现给玩家,初始化雷盘,将两个字符数组分别全部赋值为字符0和字符*,打印棋盘,随机设置雷所在位置,根据玩家输入的坐标

随机推荐