0%

桶排序

发表于 更新于 分类于
本文字数： 689 阅读时长 ≈ 1 分钟
时间复杂度为O(n)的排序

桶排序(Bucket Sort)是时间复杂度为O(n)的排序

前言

排序算法是每个程序员应该掌握的。

适用范围

待排序的元素能够均匀分布在某一个范围[MIN, MAX]之间。

空间复杂度

桶排序需要两个辅助空间：

  1. 第一个辅助空间，是桶空间B

  2. 第二个辅助空间，是桶内的元素链表空间

总的来说，空间复杂度是O(n)。

关键步骤

桶排序有两个关键步骤:

  1. 扫描待排序数据A[N]，对于元素A[i]，放入对应的桶X
  2. A[i]放入桶X，如果桶X已经有了若干元素，使用插入排序，将arr[i]放到桶内合适的位置

桶X内的所有元素，是一直有序的

插入排序是稳定的，因此桶内元素顺序也是稳定的。

PS: 桶排序是一种思想，桶里面的排序其实并不一定非得是插入排序。
将数组元素分配到多个桶后，可以使用不同的排序算法或递归应用桶排序算法，将每个桶单独排序。

当arr[N]中的所有元素，都按照上述步骤放入对应的桶后，就完成了全量的排序。

举个例子

假设待排序的数组均匀分布在[0, 99]之间：

{5,18,27,33,42,66,90,8,81,47,13,67,9,36,62,22}

可以设定10个桶，申请额外的空间bucket[10]来作为辅助空间。其中，每个桶bucket[i]来存放[10 * i, 10 * i + 9]的元素链表。

上图所示:

  • 待排序的数组为unsorted[16]
  • 桶空间是buket[10]
  • 扫描所有元素之后，元素被放到了自己对应的桶里
  • 每个桶内，使用插入排序，保证一直是有序的

总结

桶排序(Bucket Sort)，总结:

是一种复杂度为O(n)的排序

是一种稳定的排序

适用于数据均匀分布在一个区间内的场景

参考链接