quicksort - 快速排序粉碎的例子

Question

我知道快速排序不是稳定的方法，即对于相等的元素，数组的成员可能不会放置在正确的位置，我需要数组的示例（其中元素重复多次）快速排序不起作用（例如需要三种方式的划分方法）。我无法在互联网上找到这样的阵列示例，您能帮帮我吗？

当然我可以使用其他类型的排序方法来解决这个问题（如堆排序，合并排序等），但我的态度是在现实世界的例子中知道，什么样的数据包含快速排序的风险，因为众所周知，这是最有用的方法，经常使用

score 2 · Accepted Answer

无论给出什么数组，快速排序都不应该崩溃。

当排序算法被称为“稳定”或“不稳定”时，它并不是指算法的安全性或它是否崩溃。它与维护具有相同键的元素的相对顺序有关。

举个简单的例子，如果你有：

[9、5、7、5、1]

然后一个“稳定”的排序算法应该保证在排序后的数组中，前 5 个仍然放在第二个 5 之前。即使对于这个简单的例子没有区别，但有些例子会有所不同，例如在排序时基于一列的表（您希望其他列保持与以前相同的顺序）。

1 回答 1