基数排序

基本思想

原理和桶排序有些类似，不过基数排序每次按照不同的规则多次使用桶，然后达到排序的目的。

示例

[19,30,28,51,44,62,7,68,85,17]

1. 首先将序列根据个位数的值装入标号为0到9的十个桶中
   0 30
   1 51
   2 62
   3
   4 44
   5 85
   6
   7 7 17
   8 28 68
   9 19
2. 依次取出这些序列，组成新的序列[30,51,62,44,85,7,17,28,68,19]，然后根据十位数的值依次的装入桶中。如果没有十位数，则是0.
   0 7
   1 17 19
   2 28
   3 30
   4 44
   5 51
   6 62 68
   7
   8 85
   9
3. 取出这些值，组成新的序列[7,17,19,28,30,44,51,62,68,85],则这个新的序列就是排序完成的。

python代码实现

#!/usr/bin/python
# encoding: utf-8

import random


# 基数排序
def radixSort(alist):
    # 列表中最大值的位数
    m = max(alist)
    d = 0
    while m > 0:
        d += 1
        m = m // 10
    # d轮装桶
    for k in xrange(d):
        # 构造10个桶
        bucket = [[] for i in xrange(10)]
        # 装桶
        for i in alist:
            bucket[i/(10**k)%10].append(i)
        # 取出桶中的值，更新序列
        alist = [j for i in bucket for j in i]
    return alist


if __name__ == '__main__':
    # 随机生成10000个1到999的数
    alist = [random.randint(1, 999) for i in xrange(10000)]
    alistNew = radixSort(alist)
    print alistNew