内部排序算法:基数排序
基本思想
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
基数排序可以采用两种方式:
我们以LSD方式为例,从数组R[1..n]中每个元素的最低位开始处理,假设基数为radix,如果是十进制,则radix=10。基本过程如下所示:
计算R中最大的元素,求得位数最大的元素,最大位数记为distance; 对每一位round =distance,计算R[i] % radix即可得到; 将上面计算得到的余数作为bucket编号,每个bucket中可能存放多个数组R的元素; 按照bucket编号的顺序,收集bucket中元素,就地替换数组R中元素; 重复2~4,最终数组R中的元素为有序。算法实现
基数排序算法,Java实现,代码如下所示:
public abstract class Sorter {排序过程
假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49},数组大小为20,我们以该数组为例,
最大的数组元素的位数为2,所以需要进行2轮映射(映射到对应的桶中),执行基数排序的具体过程,如下所示:
数组的原始顺序,如下图所示:
![radixsorter-array-original](http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/04/radixsorter-array-original.png)
数组中存在的相同的元素(同一个待排序的数字出现大于1次),我们使用不同的背景颜色来区分(红色背景表示第二次出现,靛青色表示第三次出现),如果一个元素只出现过一次,则我们就使用一种固定的颜色(浅绿色)表示。
根据数组元素个位数字将数组中元素映射到对应的桶中(bucket)
我们使用的是十进制,基数(Radix)自然是10,根据数组元素个位数的,应该映射到10个桶中,映射后的结果,如图所示:
![radixsorter-bucket-1](http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/04/radixsorter-bucket-1.png)
在映射到桶的过程中,从左到右扫描原始数组。因为映射到同一个桶中的元素可能存在多个,最多为整个数组的长度,所以在同一个桶中,要保持进入桶中的元素的先后顺序(先进的排在左侧,后进的排在右侧)。 收集桶中元素,并在原始数组中原地替换,使数组中元素顺序重新分布
扫面前面已经映射到各个桶中的元素,满足这样的顺序:先扫描编号最小的桶,桶中如果存在多个元素,必须按照从左到右的顺序。这样,将得到的数组元素重新分布,得到一个元素位置重新分布的数组,如图所示:
![radixsorter-array-after-collecting-1](http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/04/radixsorter-array-after-collecting-1.png)
这时,可以看到元素实际上是按照个位的数字进行了排序,但是基于整个元素来说并不是有序的。 根据数组元素十位数字将数组中元素映射到对应的桶中(bucket)
这次映射的原则和过程,与前面类似,不同的是,这次扫描的数组是经过个位数字处理重新分布后的新数组,映射后桶内的状态,如图所示:
![radixsorter-bucket-2](http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/04/radixsorter-bucket-2.png)
和前面收集方法类似,得到的数组及其顺序,如图所示:
![radixsorter-array-after-collecting-2](http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/04/radixsorter-array-after-collecting-2.png)
我们可以看到,经过两轮映射和收集过程,数组已经变成有序了,排序结束。
算法分析
时间复杂度设待排序的数组R[1..n],数组中最大的数是d位数,基数为r(如基数为10,即10进制,最大有10种可能,即最多需要10个桶来映射数组元素)。处理一位数,需要将数组元素映射到r个桶中,映射完成后还需要收集,相当于遍历数组一遍,最多元素书为n,则时间复杂度为O(n+r)。所以,总的时间复杂度为O(d*(n+r))。
空间复杂度设待排序的数组R[1..n],数组中最大的数是d位数,基数为r。基数排序过程中,用到一个计数器数组,长度为r,还用到一个r*n的二位数组来做为桶,所以空间复杂度为O(r*n)。
排序稳定性通过上面的排序过程,我们可以看到,每一轮映射和收集操作,都保持从左到右的顺序进行,如果出现相同的元素,则保持他们在原始数组中的顺序。
可见,基数排序是一种稳定的排序。
基数排序的原理与实现 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。 比较型排序:常见的快速排序,归并排序,冒泡排序……等等,都是基于比较的排序算法。比较型排序算法时间复杂度下界为O(N*log2N) ,而非比较型排序算法有:计数排序,桶排序,基数排序等;其中,计数排序,桶排序的时间复杂度分别为O(n+m)和O(n),线性的时间复杂度。
demo地址:https://github.com/weiman152/PaiXu.git 插入排序是一种局部有序的算法。插入排序把待排序的数组分成两部分,前半部分是有序的,但不是绝对有序,因为后面的数据还有可能插进来,改变现有顺序。
demo地址:https://github.com/weiman152/PaiXu.git 选择排序是先比较,并不急着交换,而是记录最小的值的位置,把最小的值与第一个位置的值进行交换。
相关文章
- 排序算法(选择、冒泡、插入、快速、希尔、归并、堆排序)
- 内部排序算法:希尔排序
- 内部排序算法:冒泡排序
- 内部排序算法:直接插入排序
- 各种排序(数据结构复习之内部排序算法总结)
- Java实现 蓝桥杯 算法提高 分解质因数(暴力)
- java算法集训结果填空题练习1
- Java实现 蓝桥杯VIP 算法提高 勾股数
- Java实现 蓝桥杯VIP 算法训练 装箱问题
- Python排序搜索基本算法之归并排序实例分析
- 算法常识——鸡尾酒排序
- EasyDarwin开源流媒体服务器低延时直播之转发缓存跟进算法
- 数据结构与算法之美-5 排序算法2 [MD]
- 【LeetCode算法-38】Count and Say
- 重新整理数据结构与算法(c#)—— 算法套路分治算法[二十五]
- 带你掌握4种Python 排序算法
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-插入排序
- 递归算法的时间复杂度分析
- 最小生成树-普利姆(Prim)算法
- 2023年中职网络安全竞赛逆向算法任务
- 图解排序算法(四)之归并排序
- 排序算法之插入排序