基数排序是按照低位先排序，然后收集; 再按照高位排序，然后再收集; 依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序， 分别收集，所以是稳定的。

import random


class phone_num(object):
    num = ""

    def __init__(self, num=""):
        self.num = num

    def get_bit(self, bit):
        return int(self.num[bit-1:bit])

    def __str__(self):
        return self.num

    def __repr__(self):
        return self.num


def radix_sort(data_list):
    radix = 11
    for i in range(radix, 0, -1):
        counting_sort(data_list, i)


def counting_sort(data_list, radix):
    length = len(data_list)
    # 定义桶
    bucket = []
    max = data_list[0].get_bit(radix)
    for i in range(length):
        if data_list[i].get_bit(radix) > max:
            max = data_list[i].get_bit(radix)

    # 初始化
    for i in range(max + 1):
        bucket.append(0)

    # 计数
    for i in range(length):
        bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] + 1

    # 累加
    for i in range(1, max+1):
        bucket[i] = bucket[i] + bucket[i-1]

    # 计数排序，定义结果数组并初始化
    result = [0 for _ in range(length)]

    # 从尾到头查找分数在result的插入位置，如果从头到尾的话就不是稳定的排序算法
    for i in range(length - 1, -1, -1):
        result[bucket[data_list[i].get_bit(radix)] - 1] = data_list[i]
        bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] - 1

    # 将结果复制到原来的数组中，达到修改数组的效果
    for i in range(length):
        data_list[i] = result[i]


def create_phone_num():
    prelist = ["130", "131", "132", "133", "134", "135", "136", "137", "138",
               "153", "155", "156", "157", "158", "159", "186", "187", "188"]
    randomPre = random.choice(prelist)
    Number = "".join(random.choice("0123456789") for i in range(8))
    phoneNum = randomPre + Number

    return phoneNum


if __name__ == "__main__":
    data_list = [phone_num(create_phone_num()) for _ in range(10)]
    print('排序前')
    for i in data_list:
        print(i)

    radix_sort(data_list)
    print("排序后")
    for i in data_list:
        print(i)


排序前
13102509815
15639884219
13736715037
15658464512
13335663937
15944723954
13498377631
13570582918
15640689458
15949340088
排序后
13102509815
13335663937
13498377631
13570582918
13736715037
15639884219
15640689458
15658464512
15944723954
15949340088

Process finished with exit code 0

基数排序的适用场景

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位 的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做 到 O(n) 了。
在实际应用中，字符串之间排序就可以使用基数排序，如果待排序的字符串位数不一致，可以通过在字符串尾部补 0 来使他们位数一致，这与小数转整数后再排序的道理是一致的。