sorting - 快速排序 - 使其稳定的条件

Question

如果排序算法保留具有相等键的任意两个元素的相对顺序，则该算法是稳定的。快速排序在什么条件下稳定？

当没有项目被传递时，快速排序是稳定的，除非它有一个较小的键。

还有什么其他条件可以使其稳定？

Answer 1

嗯，使用 O(N) 空间而不是就地、不稳定的实现所使用的 O(log N) 空间来创建稳定的快速排序是相当容易的。当然，使用 O(N) 空间的快速排序不一定是稳定的，但可以使其稳定。

我读到可以使用 O(log N) 内存进行就地快速排序，但最终会明显变慢(并且实现的细节有点糟糕)。

当然，您始终可以遍历正在排序的数组并添加一个额外的键，该键是其在原始数组中的位置。然后快速排序就会稳定，你只需遍历并删除最后多余的键即可。