简介

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

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

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

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

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

算法步骤取数组中的最大数，并取得位数；从最低位开始，依次进行一次排序；从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。复杂度时间复杂度：平均、最好、最坏都为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 dataif __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 实现经典算法之希尔排序