欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

桶排序(最快最简单的排序)

程序员文章站 2022-05-13 21:37:42
...

第十一章 23

// An highlighted block
def bucketSort(nums):
    max_num = max(nums)
   # 创建一个元素全是 0 的列表, 当做桶
    bucket = [0]*(max_num+1)
    print(bucket)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in nums:
        bucket[i]+=1
        # 存储排序好的元素
        sort_nums = []
       # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j]!=0:
            for y in range(bucket[j]):
                sort_nums.append(j)
    return sort_nums
nums = [5,6,3,2,1]
print(bucketSort(nums))

桶排序的基本思想是将一个数据表分割成许多 buckets,然后每个 bucket 各自排序,或用不同的排序算法,或者递归的使用 bucket sort 算法。也是典型的 divide-and-conquer 分而治之的策略。它是一个分布式的排序,介于 MSD 基数排序和 LSD 基数排序之间。

1、桶排序是稳定的
2、桶排序是常见排序里最快的一种, 大多数情况下比快排还要快
3、桶排序非常快,但是同时也非常耗空间,基本上是最耗空间的一种排序算法