当前位置: 首页 > 后端技术 > Python

Python实现基数排序(RadixSort)

时间:2023-03-25 22:17:15 Python

十大排序算法介绍基数排序(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来实现