quicksort算法的稳定性 [英] quicksort algorithm stability

问题描述

Quicksort不稳定，因为它交换不相邻的元素。

Quicksort is not stable, since it exchanges nonadjacent elements.

请帮助我理解此声明

我知道分区的工作原理以及稳定性。但是我不能弄清楚是什么原因使上述内容不稳定？
然后，我相信对于合并排序也可以说同样的话-尽管它被引用为一种稳定的算法。

I know how partitioning works, and what stability is. But I cant figure out what makes the above as the reason for this to be not stable? Then I believe the same can be said for merge sort - though it is quoted to be a stable algorithm.

推荐答案

请考虑以下配对对数组在分区期间发生的情况，其中比较器使用整数（仅）。字符串就在那儿，这样我们就可以比较两个元素，好像相等，但实际上是可区分的。

Consider what happens during the partition for the following array of pairs, where the comparator uses the integer (only). The string is just there so that we have two elements that compare as if equal, but actually are distinguishable.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

按定义，如果排序之后两个比较的元素看起来相等，则排序是稳定（两个 4 s）的显示顺序与之前相同。

By definition a sort is stable if, after the sort, the two elements that compare as if equal (the two 4s) appear in the same order afterwards as they did before.

假设我们选择 3 作为枢纽。两个 4 元素将在其后结束，而 1 和 2 之前（还有很多事情，我已经忽略了移动轴，因为它已经处于正确的位置，但是您说的是您了解分区）。

Suppose we choose 3 as the pivot. The two 4 elements will end up after it and the 1 and the 2 before it (there's a bit more to it than that, I've ignored moving the pivot since it's already in the correct position, but you say you understand partitioning).

Quicksorts一般不会在分区后的两个 4 给出哪里的任何特定保证，我认为大多数实现会扭转它们。例如，如果我们使用 Hoare的经典分区算法，则按以下方式对数组进行分区：

Quicksorts in general don't give any particular guarantee where after the partition the two 4s will be, and I think most implementations would reverse them. For instance, if we use Hoare's classic partitioning algorithm, the array is partitioned as follows:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

这违反了排序的稳定性。

which violates the stability of sorting.

由于每个分区都不稳定，因此总体排序不太可能。

Since each partition isn't stable, the overall sort isn't likely to be.

正如Steve314在评论中指出的那样，归并排序是稳定的，前提是在合并时，如果遇到相等的元素，则始终首先输出来自要合并在一起的两半的较低部分的元素。也就是说，每次合并必须看起来像这样，其中左是原始数组中从下到下的那一侧。

As Steve314 points out in a comment, merge sort is stable provided that when merging, if you encounter equal elements you always output first the one that came from the "lower down" of the two halves that you're merging together. That is, each merge has to look like this, where the "left" is the side that comes from lower down in the original array.

while (left not empty and right not empty):
    if first_item_on_left <= first_item_on_right:
       move one item from left to output
    else:
       move one item from right to output
move everything from left to output
move everything from right to output

如果< = 是< ，则合并将不稳定。

If the <= were < then the merge wouldn't be stable.

这篇关于quicksort算法的稳定性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！