搜索

快速排序和桶排序的区别

gecimao 发表于 2019-07-25 21:48 | 查看: | 回复:

  1【专注:Python+人工智能Java大数据HTML5培训】 2【免费提供名师直播课堂、公开课及视频教程】 3【地址:北京市昌平区三旗百汇物美大卖场2层,微信公众号:yuzhitc】

  虽然表面上看起来两者很像,桶排序是把数据分到若干个桶里,再递归地对每一个桶进行排序;上述方法一是把(除了arr[piv]以外的)数据分到前后两个“桶”里,再递归地分别进行排序。但是桶排序在把数据分桶的时候,并不是使用数据本身两两比较的方法,而是读取数据某一位上的值再两两比较。这就使得桶排序的递归深度可以是常数,而不像上述快排方法一,递归深度和数据量 n 有关。

  桶排序并不属于比较排序,也就是说它用到了快速排序、归并排序等这些排序方法所无法获取的信息。(但是你可以用比较排序的方式来实现桶排序。)如果桶排序永远只使用两个桶,它与快排的效率是一样的。但是桶排序可以使用更多(但是有限)的桶,因为我们事先已经知道数据的范围,因而知道可以用多少个桶来装。比如我们知道数据取值是0-99,就可以放心建立10个桶,按照十位上的数字(0到9)将数据分到每个桶里,而不用担心出现数据100时没有对应的桶。但是快排假设我们不知道数据的范围,因此只能把数据按照“比arr[piv]大还是小”分成两个桶。

  知道合伙人数码行家采纳数:72677获赞数:87345公司运维员工向TA提问展开全部桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

  希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。

  希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

本文链接:http://baumseelen.com/duipaixu/722.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部