Python里实现基数排序

本文主要讲解的是Python里基数排序的实现方法。

思路

  首先准备0号桶~9号桶:

    

  根据个位上的数值选择几号桶,后再将数字依次倒出桶:

      

  根据序列的顺序十位上的数值选择几号桶,后再将数字依次倒出桶:

      

  根据序列的顺序百位上的数值选择几号桶,后再将数字依次倒出桶,最后一次倒出桶的顺序就是排序的顺序:

      

Python实现

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

class RadixSort:
    def radixSort(self, A, n):
        order_array = A
        buckets = [[] for i in xrange(10)]  # 生成桶
        radix = 1  # 基数为1代表个位
        max_radix = 10 ** len(str(max(order_array)))  # 这些数的最大位
        while radix < max_radix:
            for n in order_array:
                digit = (n / radix) % 10  # 个位、十位、百位...
                buckets[digit].insert(0, n)  # 将数字添加到桶中

            i = 0
            for pour_nums in buckets:
                while pour_nums:
                    order_array[i] = pour_nums.pop()
                    i += 1
            radix *= 10
        return order_array

l = [54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28]
print RadixSort().radixSort(l, len(l))

本文来源:https://www.cnblogs.com/wangchaowei/p/8302183.html

分享:

扫一扫在手机阅读、分享本文