快速排序算法稳定性

Question

Quicksort不稳定,因为它交换不相邻的元素.

请帮我理解这个陈述.

我知道分区是如何工作的,以及稳定性是什么.但我无法弄清楚是什么导致上述不稳定的原因？然后我相信合并排序也是如此 - 尽管它被引用为一种稳定的算法.

Answer 1

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

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

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

假设我们选择3作为支点.两个4后和元素会落得1和2前(还有一点,以它比,我已经忽略了移动支点,因为它已经在正确的位置,但你说你明白分区).

一般来说,Quicksorts没有给出任何特别的保证,在分区后两个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

如果<=是<,则合并就不会稳定.

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

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

Answer 3

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