快速排序-使它稳定的条件 [英] Quicksort - conditions that makes it stable

问题描述

如果排序算法通过等号键保留任何两个元素的相对顺序，则该算法是稳定的.在哪种情况下quicksort稳定?

除非没有较小的密钥，否则没有任何项目通过时，Quicksort是稳定的.

Quicksort is stable when no item is passed unless it has a smaller key.

还有哪些其他条件使其稳定?

What other conditions make it stable?

推荐答案

好吧，使用O(N)空间而不是就地，不稳定的O(log N)进行稳定的快速排序很容易实现用途.当然，使用O(N)空间的快速排序不一定是稳定的，但是可以做到这样.

Well, it is quite easy to make a stable quicksort that uses O(N) space rather than the O(log N) that an in-place, unstable implementation uses. Of course, a quicksort that uses O(N) space doesn't have to be stable, but it can be made to be so.

我已经读到可以使用O(log N)内存进行就地快速排序，但是最终会大大降低速度(实现的细节也很糟糕).

I've read that it is possible to make an in-place quicksort that uses O(log N) memory, but it ends up being significantly slower (and the details of the implementation are kind of beastly).

当然，您总是可以遍历正在排序的数组并添加一个额外的键，该键在原始数组中的位置.然后，快速排序将变得稳定，您只需仔细检查并删除最后的多余密钥即可.

Of course, you can always just go through the array being sorted and add an extra key that is its place in the original array. Then the quicksort will be stable and you just go through and remove the extra key at the end.

这篇关于快速排序-使它稳定的条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！