简介

基数排序属于分配式排序，又称“桶子法”（bucket sort），是一种非比较型整数排序算法，最早用于解决卡片排序的问题。

其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序、计数排序（Python 实现经典算法之计数排序）、桶排序（Python 实现经典算法之桶排序）三种排序算法都利用了桶的概念，但对桶的使用方法上是有明显差异的：

• 基数排序：根据键值中的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值。

通常而言，基数排序比基于比较的排序算法（比如快速排序（Python 实现经典算法之快速排序））要快。但由于需要额外的内存空间，因此当内存空间稀缺时，原地置换算法（比如快速排序）或许是个更好的选择

算法步骤

1. 取数组中的最大数，并取得位数；
2. 从最低位开始，依次进行一次排序；
3. 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

复杂度

• 时间复杂度：平均、最好、最坏都为O(k*n),其中k为常数，n为元素个数
• 空间复杂度：O(n+k)

稳定性

基数排序是一种稳定的排序算法。

动图演示

实例代码

####
# 今日头条：技术好奇心
####

# 基数排序
def radix_sort(data):
    # 取数组中最大值
    max_num = max(data)
    # 初始位数，用于后面计算10的阶乘
    it = 0
    # 10的阶乘小于最大值则进行循环，比如第一次为1，则从个位开始
    while 10 ** it <= max_num:
        # 创建10个空桶（这里之所以是10个，是因为我们数组元素是10进制）
        buckets = [[] for _ in range(10)]
        # 循环数组
        for var in data:
            # 按照下面算法，依次取一位数作为桶序号
            # 注意：这里之所以除以10的阶乘再求余，是为了获取相应位上的数字
            key = (var // 10 ** it) % 10
            # 放入桶中
            buckets[key].append(var)
        # 清空data数组，留待下面插入数据
        # (每次会重新分配，最大多少位则分配多少次)
        data.clear()
        # 循环桶
        for buc in buckets:
            # 依次将桶中的数据合并到data数组中
            data.extend(buc)
        # 每循环一次，it初始值+1，代表向前进一位
        it += 1
    # 返回处理好的数据
    return data


if __name__ == "__main__":
    print('今日头条：技术好奇心')
    print('----------- 排序前数组内容 -----------------')
    arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127]
    print(arr)
    new_arr = radix_sort(arr)
    print('------------ 排序后的结果 ------------------')
    print(new_arr)

运行结果：

今日头条：技术好奇心
----------- 排序前数组内容 -----------------
[3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127]
------------ 排序后的结果 ------------------
[1, 7, 10, 82, 577, 743, 2030, 2599, 3138, 3221, 4127, 4793, 5622, 9420, 9680]

相关文章

Python 实现经典算法之快速排序

Python 实现经典算法之选择排序

Python 实现经典算法之插入排序

Python 实现经典算法之堆排序

Python 实现经典算法之计数排序

Python 实现经典算法之冒泡排序

Python 实现经典算法之归并排序

Python 实现经典算法之桶排序

Python 实现经典算法之希尔排序