排序算法：桶排序

发布于 10 分钟前

桶排序 (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 内的所有元素，是一直有序的；
插入排序是稳定的，因此桶内元素顺序也是稳定的；

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

桶排序的伪代码是：

bucket_sort(A[N]){
  for i =1 to n{
    将A[i]放入对应的桶B[X];
    使用插入排序，将A[i]插入到B[X]中正确的位置;
  }
  将B[X]中的所有元素，按顺序合并，排序完毕;
}

举个栗子：

假设待排序的数组均匀分布在 [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] 的元素链表。

上图所示：

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

例如，标红的元素 66, 67, 62 最终会在一个桶里，并且使用插入排序桶内保持有序。

最终，每个桶按照次序输出，排序完毕。

桶排序 (Bucket Sort)，总结：

（1）桶排序，是一种复杂度为 O(n) 的排序；
（2）桶排序，是一种稳定的排序；
（3）桶排序，适用于数据均匀分布在一个区间内的场景；

Recommend