转自:http://blog.csdn.net/weiwenhp/article/details/8617417
我们知道假如一个正整数A大于数B,要么就是A的位数更多点,要是相同位数则从高往低数起,必有某一位大于B.
基数排序就是把一待排序的元素每一位(个,十,百...)拆分出来排序.先从个位,然后再十位.那么首先肯定要确定下待排序中的元素最大数有多少位.然后再借助一个临时数组和一个计数的大小为10的数组辅助每一轮的排序。
请参考计数排序
//先计算出待排序元素最大数的位数
int MaxDigit(int* arr, int len) { int digit = 1; //所有元素小于10时的默认最大位数为1 int radix = 10; for (int i = 0; i < len; i++) //遍历整个序列 { if (arr[i] >= 10) { while (arr[i] >= radix) //当大于等于10则最大位数为2,依此类推大于等于100是3 { digit++; radix = radix * 10; } } } return digit; } void RadixSort(int* arr, int len) { int digit = MaxDigit(arr, len); //待排序数组最大元素的位数为digit int* tmpArr = new int[len]; //辅助排序的临时数组 int count[10] = { 0 }; //索引0 - 9刚好对应数字0至9 int radix = 1; int val; //计算出来的元素每一位的值 for (int i = 1; i <= digit; i++) //i是1时对个位数排序,为2时对百位数排序 { for (int j = 0; j < 10; j++)//初始化count数组为0 count[j] = 0; for (int j = 0; j < len; j++) { //计算每一位的数值,当radix为1时是个位,为100时是百位数的值 val = (arr[j] / radix) % 10; //val的值是索引0-9,每有一位元素的位数值与索引值相同则计数数组索引对应值加1 count[val] ++; } //这一步最为关键,很让人迷糊的.我们经过前面一步后,数组中每个索引对应的值是arr元素的个数. //要是把计数数组count中所有值加起来,总数应该是len. //现在用前一个值是自己本身的值相加得出的结果是左边所有 //元素个数和,这在等会映射到tmpArr中时有用 for (int j = 1; j < 10; j++) count[j] = count[j - 1] + count[j]; for (int j = len - 1; j >= 0; j--)//见备注 { val = (arr[j] / radix) % 10; tmpArr[count[val] - 1] = arr[j]; //把arr的元素映射到tmpArr,且是按位数排好序的. count[val]--; } for (int j = 0; j < len; j++) arr[j] = tmpArr[j]; //把临时数组中按位排好序的元素拿回来 radix = radix * 10; } delete[] tmpArr; }
备注:
这里要注意的是 “扫描a数组把各个元素放在有序序列相应的位置上” 这步为什么要从后往前扫描a数组呢?大家想一想计数排序的过程就知道,因为从前扫描导致计数排序不稳定,前面说了,计数排序是基数排序的基础,所以它的稳定性直接影响到基数排序的稳定。
相关推荐
直接插入排序,希尔排序,冒泡排序,快速排序,直接选择排序,堆排序,归并排序,基数排序,比较全面,转自blog.csdn.com/whuslei
此题目主要要求对汽车牌照进行基数排序,和用二分查找的思想进行查找,这两种方法思想并不难,但是要对汽车牌照进行排序和查找,此问题涉及到的主要问题是: 首先的问题就是,用何种存储结构对汽车信息和汽车牌照...
种类使用比 O(n*log(n)) 更快的混合基数排序提出的 Boost Sort 库如果您使用的是 Windows,请将下面路径中的“/”替换为“”。 要安装,下载 boost,运行 bootstrap,然后将此库复制到 /libs/sort。 仅在 Windows 上...
基数排序法 � 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 � 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵......
1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、基数排序、快速排序、归并排序。(快速排序、归并排序讲到之后再做) 3、*能够显示各种排序算法的中间过程。
此程序要完成如下要求:选择一种数据结构来存储每个车辆的信息(如车主姓名,汽车等),在此基础上进行基数排序,而汽车牌照是由汉字、字母以及数字组成,即多关键字,其中字母和数字的比较是比较容易实现的,考虑到...
经典常用算法解析与实现,通过Java C语言分别实现各种算法,图文并茂,描述很详细! 主要包括如下算法,很全面! 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) ...基数排序等
基数排序 实现图的存储结构 图的深度遍历 图的广度遍历 二叉排序树的复制 计算二叉树的结点个数 删除单链性表中值相同的多余结点 删除线性表中所有值为x的元素 Josephus问题 利用递归实现查找中序遍历序列...
老掉牙 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 ...基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜
C语言经典几十个经典案例,都有详尽 河内塔 费式数列 巴斯卡三角形 三色棋 老鼠走迷官(一) 老鼠走迷官(二) 骑士走棋盘 八个皇后 八枚银币 生命游戏 ...基数排序法 循序搜寻法(使用卫兵)
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、...
基数排序 二叉树的建立 二叉排序树的生成 二叉排序树的删除 中序线索化二叉树 寻找中序线索化二叉树指定结点的前驱 寻找中序线索化二叉树指定结点的后继 构造哈夫曼树的算法模拟 构造哈夫曼树过程 树、森林和二叉树...
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵 对...
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方...
单链表结点的删除,单链表结点的插入,图的深度优先遍历,基数排序,堆排序,头插法建单链表,寻找中序线索化二叉树指定结点的前驱,寻找中序线索化二叉树指定结点的后继,尾插法建表,希儿排序,开放定址法建立散...
基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵 稀疏矩阵 多维矩阵转一维矩阵 上三角、下三角、对称矩阵 奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵