转自: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数组呢?大家想一想计数排序的过程就知道,因为从前扫描导致计数排序不稳定,前面说了,计数排序是基数排序的基础,所以它的稳定性直接影响到基数排序的稳定。
相关推荐
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。在C++中实现基数排序,主要涉及到数组、计数排序以及位操作等技术。以下是关于基数排序及其C++实现的详细解释...
数据结构中的基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数...
### Radix Sort (基数排序) 排序算法详解 #### 一、算法介绍与应用场景 基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。递归算法则是一种解决问题的方法,它解决问题的每一个子问题都是原问题的缩小版,直到子问题简单到可以直接...
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。基数排序的名称来源...
### 对10进制数进行基数排序的数据结构与算法实现 #### 1. 基数排序概述 基数排序是一种非比较型整数排序算法,它通过整数的各位数字来分配进桶的方式来进行排序。该算法对于固定大小的整数特别有效。基数排序的...
在计算机科学中,基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、浮点数等,基数排序也不是只能用于...
基数排序算法是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体实现时,从最低位开始,也就是个位数,然后是十位、百位等等,直到最高位。在每一趟排序中,使用的是...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、日期等,所以基数排序并不是只能用于整数。 基数排序的Java实现方法RadixSort,...
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如电话号码)、日期等,基数排序并不限于整数。通常用的排序算法...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串、算法中更确切地说是将数据中的每个数按照“基数”拆分成单个单位,然后从低位到...
基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如将数字转换为字符串形式),所以基数排序也可以很自然地扩展到...
基数排序是一种非比较型整数排序算法,它的原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种算法是通过分配、收集和再分配的步骤来实现的,它不依赖于元素之间的比较,而是依赖于数字的位数。这种...
### C++实现基数排序 #### 一、基数排序概述 基数排序是一种非比较型的整数排序算法。它通过对整数的每一位进行排序来达到整体序列的有序化。该算法的特点在于它不是通过元素间的相互比较来进行排序,而是通过按...
### Java实现基数排序算法 #### 实现原理 基数排序是一种非常高效的非比较型整数排序算法,它通过按数字的各个位数进行排序来实现序列的整体有序化。该算法的关键在于能够有效地处理多位数,避免了传统的两两比较...
基数排序是一种非比较型整数排序算法,它的核心在于将数字按位进行处理,从低位到高位逐位进行排序。这种排序方式适用于处理包含整数或者可以转换为整数形式的数据,如字符串。基数排序的关键在于“计数排序”...
在探讨算法与数据结构的领域,Java编程语言提供了一种强大的工具来实现各种算法,其中包括基数排序和归并排序。基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较...
### 链表基数排序的存储空间效率优化 #### 一、优化桶结构,降低空间消耗 在链表基数排序中,桶结构的选择对于优化存储空间有着至关重要的作用。优化桶结构可以从以下几个方面入手: 1. **基于哈希表的优化桶结构...
### 时间整数格式基数排序及转换为字符串形式 在计算机科学中,基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。基数排序通常用于那些不是通过比较元素大小来...
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。它的时间复杂度为O(nk),其中n是排序的数的个数,k是数的位数。当k不大时,基数排序的效率是很高的。 冒泡...