快速排序算法的稳定性

Question

快速排序不是稳定的算法，因为它交换非相邻元素。

请帮我理解这个说法。

我知道如何进行分区以及什么是稳定性。但我无法弄清楚为什么上述原因导致它不稳定？我认为同样的情况也适用于归并排序-尽管它被引用为稳定算法。

- IUnknown

---

这意味着在多次排序中，不能保证相同相等的元素排列顺序相同。例如，如果有1、1、2、3、5、6、7，开头的两个1可能没有固定的顺序——当你按照更复杂对象的某个键进行排序时，这一点会更加重要。 - im so confused

这个问题在这里有很好的解释。 - axiom

Answer 1

考虑以下成对数组在分区过程中的情况，其中比较器只使用整数。字符串只是为了确保我们有两个元素进行比较，它们看起来相等，但实际上是可区分的。

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

根据定义，如果在排序后，比较相同的两个元素（即两个4）的顺序与排序前相同，则排序是稳定的。

假设我们选择3作为基准点。两个4元素将在其后面，而1和2将在其前面（还有一些其他细节需要注意，但由于基准点已经处于正确位置，因此我忽略了移动基准点，但你说你理解分区）。

通常情况下，快速排序不会保证分区后两个4出现在哪里，我认为大多数实现都会反转它们。例如，如果我们使用Hoare的经典分区算法，则数组被分成如下：

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

这违反了排序的稳定性。

由于每个分区都不稳定，整体排序也很可能不稳定。

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

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

如果 <= 改成 <，那么合并就不稳定了。

- Steve Jessop

---

+1 - 你可以有用地补充一下，在归并排序中，相等的元素保留其原始顺序的原因是因为在每次合并时，您知道哪个已合并的序列先出现在原始数据中 - 当找到相等的元素时，只需选择来自第一个序列的元素而非第二个，就可以保留原始的排序。因此，在某种程度上，这些项目并不相等WRT合并-当值相等时，合并根据原始位置强制执行排序。 - user180247

非常有帮助 - 现在很清楚了！！ - IUnknown

这个例子是最好的 :) - adarsh

@Steve314。哇！你还在这个网站上吗？ - Avv

Answer 2

考虑以下成对数组：

{(4,'first');(2,'');(1,'');(4,'second');(3,'')}

将3作为枢轴。在快速排序运行期间，数组经历以下变化：

1. {(4,'first');(2,'');(1,'');(4,'second');(3,'')} 2. {(2,'');(4,'first');(1,'');(4,'second');(3,'')} 3. {(2,'');(1,'');(4,'first');(4,'second');(3,'')} 4. {(2,'');(1,'');(3,'');(4,'second');(4,'first')} 5. {(1,'');(2,'');(3,'');(4,'second');(4,'first')}

显然，相对顺序已更改。这就是为什么快速排序被称为“不保证稳定性”的原因。

- sai harish

Answer 3

当一个用户拥有一个已排序的数组，并按另一列进行排序时，排序算法是否总是保留先前排序键不同但在新排序键中具有相同值的元素的相对顺序？因此，在始终保持元素顺序（在新排序键中不不同的元素）的A排序算法被称为“稳定排序”。

请查看以下示例：

- Rahul Maurya

Answer 4

如果等效项的顺序得到保留，那么排序就被称为是稳定的。快速排序的稳定性取决于分区策略。"快速排序不是稳定的，因为它交换非相邻元素。"这个说法依赖于使用 Hoare 分区的前提条件。以下是Berkeley CS61b中的一个Hoare Partitioning演示文稿：Hoare Partitioning。您应该知道 "它交换非相邻元素" 意味着什么。

- imcaozi