快速排序算法稳定性

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

请帮我理解这个说法。

我知道分区是如何工作的，以及稳定性是多少。但我不知道是什么导致上述情况成为不稳定的原因？然后我相信合并排序也是如此 - 尽管它被引用为稳定算法。

2012-11-21 IUnknown

这意味着，在多种排序中，您不能保证具有相同的等同顺序的元素。所以如果你有1,1,2,3,5,6,7，那么开始时的两个可能不是按照定义的顺序 - 当你为更复杂的对象排序某个键时，这更重要，显然 –

它[http://en.wikipedia.org/wiki/Sorting_algorithm#Stability] – axiom

考虑在分区中为以下数组对（其中比较使用整数（仅））发生了什么。该字符串就在那里，以便我们有两个比较相似的元素，但实际上是可区分的。

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

根据定义排序是稳定如果排序后，即作为比较，如果相等（两个4 S）的两个元素出现在相同的顺序之后，因为他们以前那样。

假设我们选择3作为关键。两个4元素将在它之后结束，1和2之前（除此之外还有一点，我忽略移动数据透视表，因为它已经处于正确的位置，但你说你明白分区）。

快速排序一般不会给予任何特别的保证其中分区后两个4将是，我认为大多数实现会扭转它们。

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

违反排序的稳定性：例如，如果我们使用Hoare's classic partitioning algorithm，阵列如下分配。

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

正如Steve314在评论中指出的，合并排序是稳定的，前提是合并时，如果遇到相同的元素，则始终首先输出来自您合并的两半的“下半部分” 。也就是说，每个合并都必须如下所示，其中“left”是原始数组中较低位置的一侧。

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-21 17:15:52

+1 - 你可以在mergesort中有效地添加它，原因相同的项目保持其原始顺序是因为在每次合并中，您知道哪些合并序列在原始数据中排在第一位 - 当您找到相同的项目时，只需从第一个序列中选择一个，而不是第二个序列，并保留原始顺序。所以从某种意义上来说，这些项目并不相同WRT合并 - 当值相等时，合并会执行基于原始位置的排序。 – Steve314

非常有帮助 - 现在有意义！ – IUnknown

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

Please have a look of example

来源

2015-03-14 10:02:26

考虑对以下数组：

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

考虑3作为枢轴。在快速排序的运行，所述阵列进行以下变化：

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

从上述

显然，相对顺序被改变。这就是为什么快速分类被认为“不能确保稳定”的原因。

来源

2016-05-18 11:48:19

快速排序算法稳定性

回答

相关问题