内容简介:排序,面试中考察基本功问的比较多的问题。时间复杂度为O(n)的排序,常见的有三种:
排序,面试中考察基本功问的比较多的问题。
时间复杂度为O(n)的排序,常见的有三种:
-
基数排序 (Radix Sort)
-
计数排序 (Counting Sort)
-
桶排序 (Bucket Sort)
今天,1分钟,争取让大家搞懂 桶排序 。
画外音:百度“桶排序”,很多文章是错误的,本文内容与《算法导论》中的桶 排序 保持一致。
桶排序的适用范围是,待排序的元素能够 均匀分布在某一个范围[MIN, MAX]之间 。
画外音:很多业务场景是符合这一场景,待排序的元素在某一范围内,且是均匀分布的。
桶排序需要两个辅助空间:
-
第一个辅助空间,是 桶空间 B
-
第二个辅助空间,是 桶内的元素链表空间
总的来说,空间复杂度是O(n)。
桶排序有两个关键步骤:
-
扫描待排序数据A[N],对于元素A[i], 放入对应的桶X
-
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]的元素链表。
上图所示:
-
待排序的数组为unsorted[16]
-
桶空间是buket[10]
-
扫描所有元素之后,元素被放到了自己对应的桶里
-
每个桶内,使用插入排序,保证一直是有序的
例如,标红的元素 66, 67, 62 最终会在一个桶里,并且使用插入排序桶内保持有序。
最终,每个 桶 按照 次序输出,排序完毕 。
神奇不神奇!!!
桶排序(Bucket Sort),总结:
-
桶排序,是一种 复杂度为O(n) 的排序
-
桶排序,是一种 稳定的 排序
-
桶排序,适用于数据均匀分布在一个区间内的场景
希望这一分钟,大家有收获。
架构师之路 -分享 可落地 的技术文章
推荐阅读:
《 拜托,面试别再问我基数排序了! 》
《 拜托,面试别再问我计数排序了! 》
至此,三种常见的时间复杂度为O(n)的 排序算法 介绍完毕。希望面试能帮到大家。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 拜托,面试别再问我 TopK 了
- 拜托!面试请不要再问我Spring Cloud底层原理
- 拜托,面试请不要再问我TCC分布式事务的实现原理!
- 拜托,面试请不要再问我分布式搜索引擎的架构原理!【石杉的架构笔记】
- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
- 排序算法下——桶排序、计数排序和基数排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Introduction to Computer Science Using Python
Dierbach, Charles / 2012-12 / $ 133.62
Introduction to Computer Science Using Python: A Computational Problem-Solving Focus introduces students to programming and computational problem-solving via a back-to-basics, step-by-step, objects-la......一起来看看 《Introduction to Computer Science Using Python》 这本书的介绍吧!