RadixSort
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到 1887 年 Herman Hollerith 在打孔卡片制表机(Tabulation Machine)上的贡献。
基数排序(Radix sort)
基本原理
将所有待比较正整数统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始进行基数为 10 的计数排序,一直到最高位计数排序完后,数列就变成一个有序序列(利用了计数排序的稳定性)。
算法步骤
- 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零
- 从最低位开始,依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
动画演示
参考实现
1 | import java.util.Arrays; |
复杂度分析
排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
基数排序 | \(O(nm)\) | \(O(nm)\) | \(O(nm)\) | \(O(n+m)\) | Out-place | 稳定 |
m 为数组中数字的最大位数
References
-
2019-05-24
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
-
2019-05-24
桶排序(Bucket sort)或箱排序(Bin sort),是一个排序算法,工作的原理是将数组分到有限数量的桶里。每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是 鸽巢排序 的一种归纳结果。
-
2019-05-24
在计算机科学中,选择排序(Selection sort)是一种排序算法,切确的说是就地比较排序。它具有 \(O(n^2)\) 时间复杂度,使其在大型列表上效率低下,并且通常比类似的插入排序更差。选择排序因其简单性而着称,并且在某些情况下具有优于更复杂算法的性能优势,特别是在辅助存储器有限的情况下。
-
2019-05-24
冒泡排序(Bubble Sort) 是一种简单的排序算法,它重复遍历列表,比较相邻的两个元素,如果它们的顺序错误则交换它们。
-
2019-05-24
计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ,其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。