【算法】基数排序 Radix Sort

算法介绍

基数排序，从左或从依次取出数列中每个数的每个数位上的数，根据取出的数，依次放到对应键值的块的最后面，然后按键值大小取出所有块，作为数列的新顺序，不断重复直到取出数列中所有数的所有数位上的数，最终的数列即为排好序的数列。
基数排序按取数方向分为两种：从左取每个数列上的数，为最高位优先（Most Significant Digit first, MSD）；从右取每个数列上的数，为最低位优先（Least Significant Digit first, LSD）。
下列以LSD为例。

视频演示

视频地址：https://www.bilibili.com/video/av18980653

python代码

#-*- coding: utf-8 -*-

# 升序
def radix_sort(data):
    max_data = max(data)
    bias = 1

    # 找完最大数的最高位
    while max_data//bias > 0:
        key_dict={}
        for d in data:
            key = int(data[i] // bias) % 10 # 依次取出个、十、百……位数
            if key not in key_dict:
                key_dict[key] = []
            key_dict[key].append(d)
        data = []
        for key in range(10):
            if key in key_dict:
                data.extend(key_dict[key])
        bias *= 10
    return data

if __name__ == '__main__':
    data = [170, 45, 90, 802, 24, 2, 66]
    sorted_data = radix_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

基数排序的时间复杂度为O(n)

注：虽然基数排序时间复杂度为O(n)，优于快速排序的O(nlogn)，但是实际使用哪个算法时，不能简单看时间复杂度，要把各种常数k都算进来。