Home

LinkWorld Algorithm Blog

15 Sep 2019

基数排序算法

基数排序算法

算法具体的介绍可以查看：排序算法（九）：基数排序

基数排序算法基于桶排序，根据待比较的数字位数进行多次的桶排序，比如从个位开始，根据个位的值填充到Key-Value容器中。

代码实现

Python实现

import math


class RadixSort:

    @staticmethod
    def sort(array):
        index, max_item, level = RadixSort.find_max(array)
        print(index, max_item, level)

        for l in range(level):
            bucket = RadixSort.init_dict()
            # 取数据
            for i, item in enumerate(array):
                # 假如item为123，当l是1的时候：
                # item -> 123,math.pow(10, l + 1) -> 100,math.pow(10, l) -> 10
                # item % math.pow(10, l + 1) -> 123 % 100 
                #                            -> 23
                # item % math.pow(10, l + 1) // math.pow(10, l) -> 23 // 10 
                #                                               -> 2
                key = math.floor(item % math.pow(10, l + 1) // math.pow(10, l))
                # print("原：%s，位数：%s，对应位数的值：%s" % (item, l, key))
                bucket[key].append(item)

            print(bucket)
            tmp_index = 0
            for i in range(0, 10):
                for tmp in bucket[i]:
                    array[tmp_index] = tmp
                    tmp_index = tmp_index + 1

        return array

    @staticmethod
    def init_dict():
        result = {}
        for index in range(10):
            result[index] = []

        return result

    @staticmethod
    def find_max(array):
        index = 0
        max_item = array[index]

        for i, item in enumerate(array):
            if item > max_item:
                index = i
                max_item = item

        # 最大数的位数
        level = 0
        temp_item = max_item
        while temp_item != 0:
            level = level + 1
            temp_item = temp_item // 10

        return index, max_item, level


def main():
    array = [
        3, 3, 3, 7, 9, 122344, 4656, 34, 34, 4656, 
        5, 6, 7, 8, 9, 343, 57765, 23, 12321
    ]
    # array = [5, 3, 2, 1, 9, 8, 4, 0]
    print("基数排序：%s" % RadixSort.sort(array))

输出结果

# 最大的数的索引，最大的数，最大的数的位数
5 122344 6
# 下面输出的数据是每次进行桶排序的数据的分布情况
# （这里进行格式化了，正常输出的一行的）
# 个位（个位都3的都在同一个数组中，比如3: [3, 3, 3, 343, 23]）
{
	0: [],
	1: [12321],
	2: [],
	3: [3, 3, 3, 343, 23],
	4: [122344, 34, 34],
	5: [5, 57765],
	6: [4656, 4656, 6],
	7: [7, 7],
	8: [8],
	9: [9, 9]
}
# 十位
{
	0: [3, 3, 3, 5, 6, 7, 7, 8, 9, 9],
	1: [],
	2: [12321, 23],
	3: [34, 34],
	4: [343, 122344],
	5: [4656, 4656],
	6: [57765],
	7: [],
	8: [],
	9: []
}
# 百位
{
	0: [3, 3, 3, 5, 6, 7, 7, 8, 9, 9, 23, 34, 34],
	1: [],
	2: [],
	3: [12321, 343, 122344],
	4: [],
	5: [],
	6: [4656, 4656],
	7: [57765],
	8: [],
	9: []
}
# 千位
{
	0: [3, 3, 3, 5, 6, 7, 7, 8, 9, 9, 23, 34, 34, 343],
	1: [],
	2: [12321, 122344],
	3: [],
	4: [4656, 4656],
	5: [],
	6: [],
	7: [57765],
	8: [],
	9: []
}
# 万位
{
	0: [3, 3, 3, 5, 6, 7, 7, 8, 9, 9, 23, 34, 34, 343, 4656, 4656],
	1: [12321],
	2: [122344],
	3: [],
	4: [],
	5: [57765],
	6: [],
	7: [],
	8: [],
	9: []
}
# 十万位
{
	0: [3, 3, 3, 5, 6, 7, 7, 8, 9, 9, 23, 34, 34, 343, 4656, 4656, 12321, 57765],
	1: [122344],
	2: [],
	3: [],
	4: [],
	5: [],
	6: [],
	7: [],
	8: [],
	9: []
}
基数排序：[3, 3, 3, 5, 6, 7, 7, 8, 9, 9, 23, 34, 34, 343, 4656, 4656, 12321, 57765, 122344]

附录

  • 时间复杂度：$O(d(n+r))$
    • $d$是最大数的位数
    • $n$是填充到KV容器（桶）循环的次数
    • $r$是填补回原数组的次数
  • 空间复杂度：$O(r)$
  • 稳定性：稳定
  • 复杂度：实现较为复杂

博文

Til next time,
LinkWorld at 15:31

scribble
‹ ›