[数据结构与算法]Python 桶排序

Python 桶排序

线性排序：

线性排序即排序算法的时间复杂度是线性的，也就是 O(n)。桶排序、计数排序、基数排序这三个算法是不基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序（Bucket sort）

桶排序(Bucket sort)是一种通过分桶和合并实现的排序算法，又被称为箱排序。
桶排序，顾名思义，会用到「桶」，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

算法步骤

设置固定数量的空桶；
把数据放到对应的桶中；
对每个不为空的桶中数据进行排序；
拼接不为空的桶中数据，得到结果。

Python 桶排序

def bucket_sort(array):
    min_num, max_num = min(array), max(array)
    bucket_num = (max_num-min_num) // 3 + 1
    buckets = [[] for _ in range(bucket_num)]
    for num in array:
        buckets[num-min_num) // 3].append(num)
    new_array = list()
    for i in buckets:
        for j in sorted(i):
            new_array.append(j)
    return new_array
 
 
if __name__ == '__main__':
    array = [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 8]
    print(bucket_sort(array))

运行结果：

[2, 2, 3, 3, 5, 5, 5, 7, 7, 7, 8, 9]

代码中的 i 表示第 i 个桶，j 表示对桶内数据排序后的第 j 个数据。

# File: bucket_sort.py
def bucket_sort(array, n):
    # 1.创建n个空桶
    new_list = [[] for _ in range(n)]

    # 2.把arr[i] 插入到bucket[n*array[i]]
    for data in array:
        index = int(data * n)
        new_list[index].append(data)

    # 3.桶内排序
    for i in range(n):
        new_list[i].sort()

    # 4.产生新的排序后的列表
    index = 0
    for i in range(n):
        for j in range(len(new_list[i])):
            array[index] = new_list[i][j]
            index += 1
    return array


def main():
    array = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
    n = len(array)
    array = bucket_sort(array, n)
    print(array)

if __name__ == '__main__':
    main()

如何使用

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

应用：

如何根据年龄给 100 万用户排序

现在你有 10 个接口访问日志文件，每个日志文件大小约 300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这 10 个较小的日志文件，合并为 1 个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有 1GB，你有什么好的解决思路，能“快速”地将这 10 个日志文件合并吗？

有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。

一年的全国高考考生人数为500 万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500 万元素的数组进行排序。

在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可（内存限制为2G意思是可以使用2G空间来运行程序，而不考虑本机上其他软件内存占用情况。） 关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。