python实现基数排序

淩亂°似流年 2022-05-13 05:42 128阅读 0赞

前面我们详细讲解了[基数排序算法][Link 1]，现在我们使用代码来实现，直接上代码，python代码如下

#!/usr/bin/python
    # -*- coding: utf-8 -*-
    import math
    #基数排序
    
    def radix_sort(the_list,radix=10):
        # print math.log(max(the_list), radix)
        # print max(the_list)
        i = int(math.ceil(math.log(max(the_list), radix)))
        print i
        # log(radix)max(the_list)，radix为底，max(the_list)的对数，其中radix为底数，max(the_list)为真数，这样就巧妙的获取了数字的位数
        bucket = [[] for i in range(radix)]
        # print bucket
        for i in range(1, i+1):  # i次循环
            # print(the_list)
            for val in the_list:
                # print val
                # print radix
                # print val % (radix ** i)
                # print(radix ** (i - 1))
                print "+++++++++++++++"+str(val % (radix ** i) / (radix ** (i - 1)))
                bucket[int(val % (radix ** i) / (radix ** (i - 1)))].append(val)  # 析取整数第K位数字 （从低到高）
            print bucket
            # print the_list[:]
            del the_list[:]#把列表清空但列表还在，效果同the_list=[]一样
    
            for each in bucket:
                the_list.extend(each)  # 桶合并
            # the_list=bucket
            print "======================"
            # print the_list
            bucket = [[] for i in range(radix)]
    
        return the_list
    if __name__ == '__main__':
        the_list = [10, 1, 18, 30, 23, 12, 7, 5, 18, 17]
        print "排序前：" + str(the_list)
        print "排序后：" + str(radix_sort(the_list))

我们运行一下，看下结果

排序前：[10, 1, 18, 30, 23, 12, 7, 5, 18, 17]
    2
    +++++++++++++++0
    +++++++++++++++1
    +++++++++++++++8
    +++++++++++++++0
    +++++++++++++++3
    +++++++++++++++2
    +++++++++++++++7
    +++++++++++++++5
    +++++++++++++++8
    +++++++++++++++7
    [[10, 30], [1], [12], [23], [], [5], [], [7, 17], [18, 18], []]
    ======================
    +++++++++++++++1
    +++++++++++++++3
    +++++++++++++++0
    +++++++++++++++1
    +++++++++++++++2
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++1
    +++++++++++++++1
    +++++++++++++++1
    [[1, 5, 7], [10, 12, 17, 18, 18], [23], [30], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    +++++++++++++++0
    [[1, 5, 7, 10, 12, 17, 18, 18, 23, 30], [], [], [], [], [], [], [], [], []]
    ======================
    排序后：[1, 5, 7, 10, 12, 17, 18, 18, 23, 30]

嗯，符合预期

[Link 1]: https://blog.csdn.net/stronglyh/article/details/82598186