又一个,时间复杂度为O(n)的排序!

架构师之路

共 1156字,需浏览 3分钟

 ·

2021-10-21 10:06

桶排序(Bucket Sort),是一种时间复杂度为O(n)的排序。
画外音:百度“桶排序”,很多文章是错误的,本文内容与《算法导论》中的桶排序保持一致。
 
桶排序的适用范围是,待排序的元素能够均匀分布在某一个范围[MIN, MAX]之间
画外音:很多业务场景是符合这一场景,待排序的元素在某一范围内,且是均匀分布的。
 
桶排序需要两个辅助空间:
(1)第一个辅助空间,是桶空间B;
(2)第二个辅助空间,是桶内的元素链表空间;
总的来说,空间复杂度是O(n)。
 
桶排序有两个关键步骤:
(1)扫描待排序数据A[N],对于元素A[i],放入对应的桶X;
(2)A[i]放入桶X,如果桶X已经有了若干元素,使用插入排序,将arr[i]放到桶内合适的位置;
画外音:
(1)桶X内的所有元素,是一直有序的;
(2)插入排序是稳定的,因此桶内元素顺序也是稳定的;
 
当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)桶排序,适用于数据均匀分布在一个区间内的场景;
 
希望这一分钟,大家有收获。

架构师之路-分享可落地的技术文章


推荐阅读:
这一种O(n)的排序算法
这个排序这么酷,为什么知道的人很少?
世界上最漂亮的排序算法!
浏览 21
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报