快速排序算法穩定性

快速排序不穩定，因爲它交換不相鄰的元素。快速排序算法穩定性

請幫我理解這個說法。

我知道分區是如何工作的，以及穩定性是多少。但我不知道是什麼導致上述情況成爲不穩定的原因？然後我相信合併排序也是如此 - 儘管它被引用爲穩定算法。

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

快速排序算法穩定性

回答

相關問題