十大排序算法之-＞基数排序

一、计数排序简介

基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是用0-9之间的所有整数作为键值，对数据集中的每一个数，按照从低位到高位的顺序，依次执行一次分配和收集操作。经过多次这样的操作后，数据集就变成了有序的。

基数排序是稳定排序，即相等的元素在排序后保持原有的相对位置

基数排序的时间复杂度为O(nk)，其中n为待排序元素个数，k为元素的位数。当k较小时，基数排序的效率较高。

基数排序的空间复杂度为O(n+k)，需要额外的空间来存储桶。

二、Python代码实现

# -*- coding: utf-8 -*-
"""
======================================
   File Name  ： radix_sort.py
   Author     ： lanmingyong
   date       ： 2024/6/21 15:49
   Description： 基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是用0-9之间的所有整数作为键值，对数据集中的每一个数，按照从低位到高位的顺序，依次执行一次分配和收集操作。经过多次这样的操作后，数据集就变成了有序的。
                基数排序是稳定排序，即相等的元素在排序后保持原有的相对位置
                基数排序的时间复杂度为O(nk)，其中n为待排序元素个数，k为元素的位数。当k较小时，基数排序的效率较高。
                基数排序的空间复杂度为O(n+k)，需要额外的空间来存储桶。
======================================= 
"""


def radix_sort(arr):
    # 基数排序
    new_arr = arr
    new_list = [[], [], [], [], [], [], [], [], [], []]
    for i in range(len(str(max(arr)))):
        for j in new_arr:
            if i + 1 > len(str(j)):
                new_list[0].append(j)
            else:
                new_list[int(str(j)[-(i + 1)])].append(j)
        new_arr = [k for l in new_list for k in l]
        new_list = [[], [], [], [], [], [], [], [], [], []]
        print("每一位排序结果：" + str(new_arr))
    return new_arr


# 验证
# arr = [9, 6, 7, 2, 8, 1, 0, 4, 3, 0]
arr = [89, 65, 21, 8, 76, 79, 0, 86, 51, 33, 34, 8, 76, 53, 93, 88, 65, 0, 92, 56, 76, 9, 111, 0, 54, 9, 37, 94, 72, 92,
       72, 88, 44, 34, 48, 14, 22, 76, 34, 45, 50, 66, 4, 77, 41, 64, 24, 65, 99, 16, 64]

if __name__ == '__main__':
    print(radix_sort(arr))

# 执行输出
"""
每一位排序结果：[0, 0, 0, 50, 21, 51, 111, 41, 92, 72, 92, 72, 22, 33, 53, 93, 34, 54, 94, 44, 34, 14, 34, 4, 64, 24, 64, 65, 65, 45, 65, 76, 86, 76, 56, 76, 76, 66, 16, 37, 77, 8, 8, 88, 88, 48, 89, 79, 9, 9, 99]
每一位排序结果：[0, 0, 0, 4, 8, 8, 9, 9, 111, 14, 16, 21, 22, 24, 33, 34, 34, 34, 37, 41, 44, 45, 48, 50, 51, 53, 54, 56, 64, 64, 65, 65, 65, 66, 72, 72, 76, 76, 76, 76, 77, 79, 86, 88, 88, 89, 92, 92, 93, 94, 99]
每一位排序结果：[0, 0, 0, 4, 8, 8, 9, 9, 14, 16, 21, 22, 24, 33, 34, 34, 34, 37, 41, 44, 45, 48, 50, 51, 53, 54, 56, 64, 64, 65, 65, 65, 66, 72, 72, 76, 76, 76, 76, 77, 79, 86, 88, 88, 89, 92, 92, 93, 94, 99, 111]
[0, 0, 0, 4, 8, 8, 9, 9, 14, 16, 21, 22, 24, 33, 34, 34, 34, 37, 41, 44, 45, 48, 50, 51, 53, 54, 56, 64, 64, 65, 65, 65, 66, 72, 72, 76, 76, 76, 76, 77, 79, 86, 88, 88, 89, 92, 92, 93, 94, 99, 111]
"""

注：如果代码有错误欢迎指出交流，感谢！！

三、动画演示