十大排序算法介绍基数排序（RadixSort）是一种非比较整数排序算法，是桶排序的扩展。其基本思想是：将所有要比较的值统一为相同的数字长度，将数字较短的数字前面用零补齐。先按照低位排序，放入10个队列，然后使用先进先出的原则进行收集；然后按照高位排序，然后收集；依此类推，直到最高位，最后得到排序好的序列。对于一组值很小的序列，速度很快，时间复杂度达到线性，思路很巧妙。算法实现步骤获取数组中最大的数，并获取位数；在数字较短的数字前补零；assign，从个位开始，按照digit值（0-9）放入0~9桶；收集，然后将0~9桶中的数据按顺序放入数组；重复3~4的过程，直到最高位，即可完成排序。Python代码实现#radix_sort代码实现fromtypingimportListdefradix_sort(arr:List[int]):n=len(str(max(arr)))#Recordthemaximumnumbersforkinrange(n):#n轮次排序#每一轮生成10个列表bucket_list=[[]foriinrange(10)]#因为每个数字都是0~9，所以创建10个bucketforiinarr:#按第k个数字放入桶bucket_list[i//(10**k)%10].append(i)#按照当前bucket的顺序重新排列listarr=[jforiinbucket_listforjini]returnarr#testDataif__name__=='__main__':importrandomrandom.seed(54)arr=[random.randint(0,100)for_inrange(10)]print("原始数据：",arr)arr_new=radix_sort(arr)print("统计排序结果为：",arr_new)#输出结果的原始数据：[17,56,71,38,61,62,48,28,57,42]统计排序结果为：[17,28,38,42,48,56,57,61,62,71]动画演示算法分析时间复杂度设置数组$R\left[1,2,\cdots,n\right]$待排序，数组中最大的数是$k$位，基数是$r$（十进制基数是10，数字0~9，最多需要10个桶来映射数组元素）。要处理一位数字，需要将数组元素映射到$r$个桶中。映射完成后，需要进行收集，相当于遍历整个数组。遍历一位数的时间复杂度是$O(n+r)$。因此，总时间复杂度为$O((n+r)×k)$。空间复杂度在基数排序过程中，需要创建$r$个队列。在最坏的情况下，$r×n$的二维数组可能被用作桶，所以空间复杂度为$O(r×n)$。稳定性基数排序过程是分别排序和收集，不影响相等元素的相对位置，所以是稳定的。综合评价时间复杂度（平均）时间复杂度（最佳）时间复杂度（最差）空间复杂度排序方法稳定性$O((n+r)×k)$$O((n+r)×k)$$O((n+r)×k)$$O(r×n)$out-placeStable联系我们个人博客网址：http://www.bling2.cn/Github地址：https://github.com/lb971216008/使用-Python实现知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve小专栏：https://xiaozhuanlan.com/Use-Python-to-实现博客园：https:///www.cnblogs.com/用Python来实现
