爲什麼是一種「不穩定的那種」認爲是不好的

只是想知道，如果有人可以解釋爲什麼一個「不穩定的一種」被認爲是壞？基本上我沒有看到任何情況下它真的很重要。任何人都可以提供一個嗎？爲什麼是一種「不穩定的那種」認爲是不好的

2011-05-11 Maxim Gershkovich

誰認爲它「不好」？你有報價或參考或鏈接？這將有助於爲這種價值判斷提供一些背景。 – 2011-05-11 03:18:51

可能的重複[有什麼好處排序算法是穩定的？]（http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-tobe - 穩定） – nawfal 2014-06-13 15:59:47

如果你有一個圖形用戶界面，允許人們通過單擊該列進行排序的單個列，並使用一個穩定的排序，那麼誰知道人們可以列通過點擊獲得多列排序A，B，C在列C，B，A上依次排列。因爲排序是穩定的，所以當你點擊B時，在B下有相同鍵的任何記錄仍然會被C排序，所以在點擊B之後，記錄按B，C排序。同樣，在你點擊A之後，記錄被排序（不幸的是，上次我在某些微軟產品或其他產品上試用過這款產品時，它看起來好像沒有使用穩定的排序方式，所以這並不奇怪）。

來源

2011-05-11 03:56:06 mcdowella

很好的例子。但是，你的意思是說有一個微軟產品不穩定？令人震驚！ :) – 2011-05-11 17:15:02

很高興我讀到這個。我不會想到這樣的事情不會使用可靠的排序。 – 2012-08-14 14:34:07

但是，通過添加一個rownum/index或其他類型的唯一計數器作爲複合排序鍵中的最後一個元素，總是不能穩定排序嗎？除非我錯過了一些東西，否則似乎微不足道。 – drake7707 2015-02-14 15:53:14

試想一下，你想組織的一副牌。您可以先按西裝排序，然後按數字值排序。如果你使用穩定的排序，你就完成了。如果你使用了不穩定的排序，那麼他們會按數字順序排序，但套裝會再次混亂。有很多相同的情況出現在實際的開發問題中。

來源

2011-05-11 03:11:45

我不認爲這是一個很好的比較，因爲任何比較函數都應考慮套裝和數量。還要注意，如果你使用穩定的排序方法，你必須按數字排序，然後適合，但不是其他方式。 – 2011-05-11 03:15:40

我不是跟着你，@比利。首先，如果且沒有穩定的排序，您需要一個比較函數來考慮這兩個因素。否則，你可以有一個簡單的比較函數，它在動態語言中可以一般地寫成按名稱排序。其次，你似乎覺得只有一種方法來組織一副牌。我向你保證，「組織」可以用多種方式來解釋。 – 2011-05-11 04:02:33

只是有你需要一個排序算法這是穩定的少數情況下。一個例子就是如果你正在實現一個基類排序，這取決於用作構建塊的比較排序算法是穩定的。（基數排序可以在線性時間內運行，但其輸入比比較排序算法更受限制（比較排序需要O（n lg n）時間））

不一定不穩定的排序是「不好」 ;更多的是穩定的那種「在某些情況下是可取的」。這就是編程語言的原因，例如C++的標準模板庫，提供 - 例如std::sort和std::stable_sort - 可讓您指定何時需要穩定性，何時不需要。

來源

2011-05-11 03:21:00

@Downvoter：這個答案究竟有什麼問題？ – 2011-06-29 21:36:38

不知道誰是downvoted，但我想他們發現你使用穩定的排序來執行另一種排序的例子有點不典型。 – Mehrdad 2012-08-14 10:35:29

「，這取決於用作構建塊的比較[基於]排序算法是穩定的想法」 - 你在說什麼？什麼是基數排序的「構建塊」，爲什麼它需要穩定？無論是否有意義，在某些情況下，排序並不是一個很好的例子，說明爲什麼穩定排序是可取的。 – Dukeling 2013-12-01 18:39:33

因爲他們可以做得比我能做的......從Developer Fusion：

有兩種排序算法0：「穩定排序」和「不穩定排序」。這些術語是指當兩個的值相等時所採取的操作。如果你有數組T0..size有兩個元素Tn的和Tk對於n < K，和這兩個元素比較平等，穩定排序它們將出現在與在Tn的價值排序輸出在Tk之前的。輸出訂單保留原始輸入訂單。一個不穩定排序，相比之下，有沒有輸出這兩個元素的順序的保證。

需要注意的是，如快速排序排序算法並不穩定或不穩定。實施將決定它是哪一個。

在任何情況下，穩定不一定比不穩定好還是壞 - 它只是有時你需要的順序的兩個相等的元素的保證。當你做需要保證時，不穩定將不適合。

來源

2011-05-11 03:22:11 JasCav

我想OP理解這兩種排序之間的區別是什麼。他在問爲什麼一種不穩定的東西會是「壞的」 - 這意味着他知道是什麼使得一種不穩定的東西。 – 2011-05-11 03:23:07

@比利 - 非常真實。我想，爲了更好的回答，我想明確說明它是什麼，所以我可以說我的最後一段 - 除了特定情況下，其中一段不一定是「壞」或「好」。 – JasCav 2011-05-11 03:24:36

爲什麼是一種「不穩定的那種」認爲是不好的

回答

相關問題