问在Bucket Sort中使用Quick Sort时，Bucket Sort是否稳定？
EN

Stack Overflow用户

提问于 2021-06-03 17:38:45

回答 1查看 42关注 0票数 1

最近，我正在学习排序算法。在学习Bucket Sort时，我遇到了标题的问题。我知道Quick Sort是不稳定的，维基说Bucket Sort在here中是稳定的。但是，在Bucket Sort中使用Quick Sort时，它是否仍然稳定？我无法想象会发生什么，有人能帮我吗？非常感谢。

回答已采纳

发布于 2021-06-03 17:54:39

任何不稳定的排序都可能改变存储桶中的项目顺序。当您合并存储桶时，此违反的顺序将保留。

假设我们有具有点(5,5)的存储桶0..9，并且存储桶20..29包含点(22,3), (21,14), (22,7)。在不稳定排序(按第一个键)之后，我们可以看到类似(21,14), (22,7), (22,3)的顺序(仅举个例子)。合并后我们可以看到

 (5,5), (21,14), (22,7), (22,3)

其中与x=22的点的相互顺序已更改

例如，如果我们在存储桶中使用插入排序，我们可以保证结果是

 (5,5), (21,14), (22,3), (22,7)

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/67819040

复制

相似问题

问在Bucket Sort中使用Quick Sort时，Bucket Sort是否稳定？EN