python算法—基数排序

基数排序

• 1.基数排序(radix_sort)
• ２.算法思想
• ３.基本解法
• 4.代码实现

1.基数排序(radix_sort)

基数排序也是非比较的排序算法，基数排序也称为桶排序。

基数排序就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字； 第1个排序关键字，第2个排序关键字，第3个排序关键字…然后，根据子关键字对待排序数据进行排序。

２.算法思想

基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。

分类

LSD——从低位向高位排

MSD——从高位向低位排

３.基本解法

第一步

以LSD为例，假设原来有一串数值如下所示:

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中:

例如：73个位数是3，放到3号桶，22个位数是2，放到2号桶…

个位数　　元素值

1 　　81

2 　　22

3 　　73 93 43

4 　　14

5 　　55 65

6

7

8 　　28

9 　　39

第二步

接下来将这些桶子中的数值重新串接起来，成为以下的数列:

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配，这次是根据十位数来分配:

十位数 　元素数值

1 　　　14

2 　　　22 28

3 　　　39

4 　　　43

5 　　　55

6 　　　65

7 　　　73

8 　　　81

9 　　　93

第三步

接下来将这些桶子中的数值重新串接起来，成为以下的数列:

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

这时候整个数列已经排序完毕;如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。

LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个"桶子"中建立"子桶"，将每个桶子中的数值按照下一数位的值分配到"子桶"中。在进行完最低位数的分配后再合并回单一的数组中。

4.代码实现

'''
先创建10个空桶，用于表示个位上，十位上，...,的数,先按个位数分好桶，
个位数=0进0号桶，个位数=1进1号桶，...,然后再将数归位，再按十位数进行分桶，
分好后归位，再按百位数进行分桶...,以此类推
'''


def radix_sort(arr):
    maxi = max(arr)  # 先找出最大数
    d = 0  # d表示最大数的位数(即循环的次数)
    while 10 ** d <= maxi:
        buckets = [[] for _ in range(10)]  # 创建 10个空桶
        for value in arr:
            # 分桶,  对于895，当d=1时,执行第二次循环，看的是十位上的数，就需要取9出来分到9号桶
            # d=0时，取5，895//1->895 , 895%10->5
            # d=1时，取9，895//10->89 , 89%10->9
            # d=2时，取8，895//100->8 , 8%10->8
            # 规律：1可以看成10的0次方，10可以看成10的1次方，100可以看成10的2次方，即10的d次方
            digit = (value // (10 ** d)) % 10  # 分别取出个位上、十位上、百位上...等的数
            buckets[digit].append(value)
        # 分桶完成
        arr.clear()
        for buc in buckets:  # buc表示每个桶，是个一维列表
            arr.extend(buc) # arr.extend(buc):表示把两个一维列表合并为一个一维列表
        d += 1


if __name__ == '__main__':
    numbers = [10, 20, 1, 2, 5, 8, 999, 65, 63, 98, 587, 695, 21, 4]
    radix_sort(numbers)
    print(numbers)
    
           

补充：二维列表的遍历

buckets=[[1,2,3],[2,4,6],[7,8,9]]
for buc in buckets:
    print(buc)
           

输出结果：

[1,2,3]
[2,4,6]
[7,8,9]
           

遍历二维列表中的每个元素

# 第一种方法遍历
list=[[1,2,3],[4,5,6],[7,8,9]]
for i in range(len(list)):
	for j in range(len(list[i])):
		print(list[i][j])
		
输出结果：
1
2
3
4
5
6
7
8
9

           

# 第二种方式遍历：
list=[[1,2,3],[4,5,6],[7,8,9]]
for arr in list:
	for element in arr:
		print(element)

输出结果：
1
2
3
4
5
6
7
8
9

           

注：arr.extend(buc)和 arr.append(buc)区别

arr=[1,2,3]
buc=[4,5,6]
arr.extend(buc)  # 把 buc列表中的元素添加到 arr列表中
print(arr)

输出结果：
[1, 2, 3, 4, 5, 6]

           

arr=[1,2,3]
buc=[4,5,6]
arr.append(buc)  # 把 buc列表添加到 arr列表中
print(arr)

输出结果：
[1, 2, 3, [4, 5, 6]]