如何將非穩定排序轉換爲穩定算法？

我搜索了太多，但我找不到注意。如何將非穩定排序轉換爲穩定算法？

提出的算法，使所有非穩定的排序算法的工作是穩定的排序算法？

來源

2015-09-13 mama23n

有在維基百科條目進行排序排序算法一張大桌子。它表明哪些是穩定的，哪些不穩定。在你使用stackoverflow之前，你有沒有想過做一些家庭作業？ –

假設你使用的是什麼，通常會是一個非穩定的排序，其中一個方案是產生一組索引0到n-1的陣列，或陣列一組指針。根據數組對索引或指針進行排序，如果相等，則比較索引或指針以保留原始順序。 – rcgldr

不僅我不在尋找作業解決方案，而是在作業中提出一些問題。我想要一些算法，而不是任何類型的代碼。 @RexD – mama23n

使用額外的內存來存儲陣列的原始順序。然後在比較兩個相等元素時，在算法中使用該順序。

下面是如何使一個例子Python的list.sort穩定：

def make_stable(algorithm): 
    def stable_version(A): 
     #adding original order of the array 
     A2 = [(y, x) for x, y in enumerate(A)] 

     #running algorithm in modified array 
     algorithm(A2) 

     #replacing original array with the result only 
     A[:] = [y for y, x in A2] 

    return stable_version 

A = [3, 2, 1, 2] 
stable_sort = make_stable(list.sort) 
stable_sort(A) 
print A

來源

2015-09-13 18:26:43

我覺得這裏有點不對勁！我試圖更好地描述它@Rex。請閱讀它 – mama23n

這是一個正確的答案。基本上，你做2元組和排序，如果元組的第一個元素相等，然後比較第二個元組。畢竟你只是扔掉第二個元素。 –

Python的排序正確地對元組進行排序。這也是一個穩定的排序，這是不同的。如果你想正確地對元組進行排序，你可以先對輔助鍵進行排序，然後對主鍵進行穩定排序。如果不是更早的話，這一切都是在20世紀60年代制定的。 –

有穩定的排序算法和不穩定的排序算法。你應該選擇一個穩定的算法。 Java中的Arrays.sort必須穩定。

來源

2015-09-13 18:28:55

我想我們可以在數目相同的情況下進行一些更改。一些變化就像在相同的數字上添加一個非常小的數字 – mama23n

如何將非穩定排序轉換爲穩定算法？

回答

相關問題