快速排序和桶排序的区别

快速排序和桶排序的区别

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

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

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

区别就是桶排序要求数据的长度必须完全一样，而希尔排序是非稳定排序算法。

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息