拜托,面试别再问我桶排序了!!!

  1. 云栖社区>
  2. 阿里云MVP>
  3. 博客>
  4. 正文

拜托,面试别再问我桶排序了!!!

子夜初商南 2019-08-08 23:40:15 浏览271
展开阅读全文

排序,面试中考察基本功问的比较多的问题。

时间复杂度为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]放到桶内

网友评论

登录后评论
0/500
评论
子夜初商南
+ 关注
所属云栖号: 阿里云MVP