32

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

请帮助我理解这句话。

我知道分区是如何工作的，以及稳定性是什么。但我无法弄清楚是什么原因导致上述情况不稳定？然后我相信归并排序也可以这样说——尽管它被引用为一种稳定的算法。

4

4 回答 4

48

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

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

根据定义，如果在排序之后，比较为相等的两个元素（两个s）以与之前相同的顺序出现，则排序是稳定的。4

假设我们选择3作为支点。这两个4元素将在它之后和之前结束1（2还有更多的东西，我忽略了移动枢轴，因为它已经在正确的位置，但你说你理解分区）。

一般来说，快速排序不会给出任何特定的保证，在分区之后两个4s 将在哪里，我认为大多数实现都会反转它们。例如，如果我们使用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

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

于 2012-11-21T17:15:52.873 回答
5

就像用户有一个排序数组，并按另一列排序，排序算法是否总是保留与前一个排序键不同但在新排序键中具有相同值的元素的相对顺序？因此，在始终保留元素顺序（在新的排序键中没有区别）的排序算法称为“稳定排序”。

请看示例

于 2015-03-14T10:02:26.803 回答
5

考虑以下对数组：

{(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')}

从上面可以清楚地看出，相对顺序发生了变化。这就是为什么说快速排序“不能确保稳定性”。

于 2016-05-18T11:48:19.127 回答
1

如果等价项的顺序保持不变，则称该排序是稳定的。快速排序的稳定性取决于分区策略。“快速排序不稳定，因为它交换不相邻的元素。” 此语句依赖于使用 Hoare 分区的先决条件。这是来自 Berkeley CS61b 的 Hoare Partitioning 演示， Hoare Partitioning

你应该知道“它交换不相邻的元素”是什么意思。

于 2019-03-05T01:56:43.637 回答