基数排序

发表于 分类于 ， 本文字数： 601

基数排序（RadixSort）

基数排序（Radix sort）是一种非比较型整数排序算法。

1. 基本思想

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

  • MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
  • LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

2. 实现逻辑

① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

3.演示

分步图示说明：设有数组 array = {53, 3, 542, 748, 14, 214, 154, 63, 616}，对其进行基数排序：

img

在上图中，首先将所有待比较数字统一为统一位数长度，接着从最低位开始，依次进行排序。

  • 按照个位数进行排序。
  • 按照十位数进行排序。
  • 按照百位数进行排序。

排序后，数列就变成了一个有序序列。

4. 复杂度分析

时间复杂度：O(k*N)
空间复杂度：O(k + N)
稳定性：稳定

设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏