算法：Distribute sort

站内链接:

Introduction

分配排序基本思想: 排序过程无须比较关键字, 通过用额外的空间来分配和收集来实现排序, 这是一种以空间换时间的排序算法, 一般时间复杂度都是 O(n). 所以, 一般分配排序都是用于小规模或者分类数量极少, 重合度非常之高的数据排序中, 在对时间性能要求非常之高, 对空间要求低的应用场景中.
分配排序就是类似分布式的思维, 对数据的分配, 分布, 进行一种归纳整合, 最终在进行下一步的操作, 具体见排序算法. 排序算法分类如下:

桶排序: 将数组分到有限数量的桶子里，然后对每个桶子再分别排序
基数排序: 将整数按位数切割成不同的数字, 然后按每个位数分别比较
索引排序: 根据索引来表示数据的交换, 并非一定在分配排序中使用.

桶排序

Analysis

本质上，这是一种非比较类-线性时间-分配类-排序, 桶本身就已经是具备顺序的一个个集合, 物以类聚、人以群分，社会分层始终存在，左与右的选择.

缺点：浪费空间，桶的数量
关键字：分配到各个桶、收集各个桶的信息

设置一个定量的数组当作空桶子, 当然必须有一套提前预定的规则, 这样才能知道桶数量
遍历数组, 将元素按照规则放入桶中, 数据的分配和整合
对每一个非空的桶进行其他排序
合并非空桶

动画演示

性能分析

时间复杂度: O(n + k)

空间复杂度: 最坏-O(n^2), O(n*k)

Example

def bucketSort(list1, bucket_num):
    """bucketSort:按照十位数进行桶排序，仅仅打印，不进行真正的结果返回

    :param list1:source list1
    :param bucket_num:bucket numbers
    """
    print '原始桶：'
    for value in list1:
        print value,
    print

    print '排序后的桶：'
    for i in xrange(10):
        for value in list1:
            if (value / 10) % 10 == i:
                print value,
    print

基数排序

Analysis

本质上，一种非比较类-线性时间-分配类-排序. 将整数按位数切割成不同的数字，然后按每个位数分别比较. 算法相关术语:

分量-d：所需进行桶排序的数量，每一次的基数都不一样的
单关键字：例如十进制整数，d 的值为最长位数，每次的基数都是 10
多关键字：例如扑克牌花色，d 的值为花色取值、点数，每次的基数不一样

算法过程：

NB 公司求职？好几个备胎人选？还有好几关面试？
保证每一次的桶排序，大哥我都在优先队列
此轮排序的基数都是在前一轮排序的基础上的，技术第一嘛，OK

排序方式：

LSD：低位优先排序
MSD：高位优先排序

动画演示

性能分析

时间复杂度: O(n), O(kn)

空间复杂度: O(n + k)

但是使用范围小

Example

def radixSort(list1, radix):
    """radixSort

    :param list1: 带排序数组
    :param radix: 基数, 需要提前设置
    """
    # 用K位数可表示任意整数
    # 1 首先根据radix基数(10进制, 15进制)来获取lnN的值: math.log(Max, radix)
    # 2 之后获取向上取整值: math.ceil(value)
    # 3 最后才得到桶的数量
    k = int(math.ceil(math.log(max(list1) + 1, radix)))
    for i in range(1, k + 1):
        # 设置某一位基数位时的桶
        bucket = [[] for j in range(radix)]
        for val in list1:
            bucket[val % (radix**i) // (radix**(i - 1))].append(val)
        del list1[:]

        # 桶合并
        for each in bucket:
            list1.extend(each)
    return list1