Quicksort is not stable, since it exchanges nonadjacent elements.
请帮助我理解这个声明。
我知道分区是如何工作的,以及什么是稳定性。但我无法弄清楚是什么原因导致上述情况不稳定? 然后我相信合并排序也可以这样说 - 尽管它被引用为一个稳定的算法。
最佳答案
考虑以下对数组的分区期间发生的情况,其中比较器使用整数(仅)。字符串就在那里,所以我们有两个元素,它们比较起来好像相等,但实际上是可区分的。
(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
如果<=
是<
那么合并将不稳定。
关于algorithm - 快速排序算法稳定性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13498213/