algorithm - 快速排序算法稳定性

Question

Quicksort is not stable, since it exchanges nonadjacent elements.

请帮助我理解这个声明。

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

Answer 1

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

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

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

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

Quicksorts 通常不会在 where 对两个 4 进行分区后给出任何特定的保证。 s 将是，而且我认为大多数实现都会颠倒它们。例如，如果我们使用 Hoare's classic partitioning algorithm ，数组分区如下:

(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

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