数据结构(python) —— 【19排序: 基数排序】

基数排序

1. 概述

    国庆玩得太欢脱了，一篇博文都没写，而且国庆前还参加了一个面试，拿到了一个题目，需要我们去完成，这也是没写博客的原因之一。

    闲话也不说了，今天来介绍介绍最后一个排序——基数排序。基数排序其实就是进行多关键字排序，比如对

32,34,17,15,7,46,56,42

排序,是否可以看做多关键字排序.

2. 思路

    先按个位数进行分桶，然后依次取出；再按十位数进行分桶，再取出。

3. 代码

'''
TOPIC: 基数排序
author: Blue
time: 2020-08-08
QQ: 2458682080
'''

def radix_sort(li):
    max_num = max(li)   # 有几位数做几次分桶
    it = 0              # 迭代次数(分桶次数)
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            # 987 it=1 十位=(987//10)%10=8  it=2 百位=(987//100)%10
            digit = (var // 10 ** it) % 10  # 确定这个数在哪个桶
            buckets[digit].append(var)
        # 分桶完成
        # 把数重新写回li
        li.clear()
        for buc in buckets:
            li.extend(buc)
        it += 1

import random
li = list(range(1000))
random.shuffle(li)
radix_sort(li)
print(li)
           

4. 时间复杂度

时间复杂度: O(kn)

线性时间复杂度比快速排序快

k是因为while执行k次，n是因为while里有一个循环，k=log10(n)