基数排序算法

原创

一点一线

发布于 2022-03-23 15:54:59

56100

代码可运行

文章被收录于专栏：计算机技术计算机技术

运行总次数：0

代码可运行

基数排序算法是基于数据的每一位来排序，基数排序也适用于正整数排序。正整数每一位都是从0~9，这个顺序是天然的。因此可以利用这种自然的序列进行排序。在排序过程中，我们先看个位上的数的大小，然后逐渐往高位看。

基数排序的关键点：

基数排序适用于对正整数进行排序。
需要从低位开始。从高位开始也可以，复杂度会增加。

举例说明一下基数排序的过程：

以数组61, 71, 14, 30, 18 为例

首先看个位，按顺序进行排序分成（30），（61,71），（14），（18）四组。
然后再合成一个数组为30,61,71,14,18
看十位上的数，按顺序进行排序分成（14,18），（30），（61），（71）四组。
再合成一个数组为14,18,30,61,71。

看一下python代码的实现过程：

def radix_sort(elements):
    max_unit = len(str(max(elements)))
    for i in range(max_unit):
        buckets = [[] for i in range(10)]
        for e in elements:
            unit = int(e / 10 ** i % 10)
            buckets[unit].append(e)

        del elements[:]
        for bucket in buckets:
            for d in bucket:
                elements.append(d)


if __name__ == '__main__':
    arr = [61, 71, 14, 30, 18]
    radix_sort(arr)
    print(arr)