7.基数排序

1.介绍
基数排序就是先对最后一位进行分类排序，然后再对倒数第二位进行排序，然后倒数第三位，直到最后一位，每次对每一位进行排序时，都会不断变得有序，由于每位数大小位0-9，所以我们需要10个桶来排序。

2.基数排序示意图来源：https://www.cnblogs.com/linzeliang1222/p/13796710.html

基数排序示意图

3.代码实现

import time
import random
import math
class RadixSort():
    def __init__(self):
        RadixSort.count = 0

    def GetMaxinumDigit(self):#获取列表中最大元素的位数，有几位
        maxinumdigit = 0
        for i in range(len(self.list)):
            currentnum = str(self.list[i])
            if len(currentnum) > maxinumdigit:
                maxinumdigit = len(currentnum)
        return maxinumdigit

    def GetDigit(self,num,i):#获得个位/十位/百位等 上的数
        digit = int(num/pow(10,i-1)) % 10
        return digit

    def sort(self,list):#将获得的位数放到对应的列表里
        self.list = list
        self.radixlist = [[]for i in range(10)] #10个空一维列表组成的二维列表
        while(RadixSort.count < self.GetMaxinumDigit()):
            RadixSort.count = RadixSort.count + 1
            for i in range(len(self.list)):
                currentdigit = self.GetDigit(self.list[i],RadixSort.count)
                self.radixlist[currentdigit].append(self.list[i])
            # print(self.radixlist) #放到对应的列表可看这个输出
            self.takeoutdata(len(self.list))

    def takeoutdata(self,length):#取出所有列表中有存放数字的数
        self.resultlist = []
        for i in range(10):
            if len(self.radixlist[i]) != 0:
                for j in range(len(self.radixlist[i])):
                    self.resultlist.append(self.radixlist[i][j])
                    #这里仅仅是将self.radixlist里的数据复制到self.resultlist这个列表里来，self.radixlist还是有数据的
                    #必须将其清空，可以调用下面的clear函数也可以  如 lst[n-1-i]=arr[j].pop()    如此取出
        self.list = self.resultlist
        # print(self.resultlist)
        self.clear()

    def clear(self):#清空列表！！！
        for i in range(10):
            if len(self.radixlist[i]) != 0:
                self.radixlist[i].clear()

# list = [9,44,54,138,23233,75,6,252]
l = []
print (time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()))
for i in range(80000):
    l.append(int(random.random()*100000000))
print (time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()))
a = RadixSort()
a.sort(l)
print (time.strftime("%Y-%m-%d %H:%M:%S", time.localtime()))

4.注意事项
基数排序一般不用于对有负数的列表进行排序