爲什麼這個算法穩定，我怎麼能使它不穩定？

我在問，因爲興趣，需要以某種方式瞭解如何知道算法是否穩定或不。爲什麼這個算法穩定，我怎麼能使它不穩定？

什麼意思是穩定的？ 如果兩個具有相同鍵的對象在排序後的輸出中以相同的順序出現在排序輸入數組中時，排序算法被認爲是穩定的。

如果我正確理解算法，數組的相同元素不能分配給同一個數組，所以它是一個穩定的算法。

我怎麼能使這個不穩定？我不想做很大的改變，那麼將for i = n down to 1 do更改爲for i = 1 to n do呢？我想這應該是打破它的一個方式，但我不是很確定：d

Input: Array arr with n integers, from 1 to m 
Output: Array arr sorted upwards 

Initialize Array B with length m which is set to 0 everywhere 
n <-- |arr| 
Initialize Array C with length n 
for i = 1 to n do 
    B[arr[i] <-- B[arr[i]] + 1 
end for 
for j = 2 to m do 
    B[j] <-- B[j] + B[j-1] 
end for 
for i = n down to 1 do 
    C[B[arr[i]]] <-- arr[i] 
    B[arr[i]] <-- B[arr[i]] - 1 
end for 
return C

這應該是與上面相同的代碼：

countingsort(A, k) 
{ 
    C = array(0, k) 
    for (m=0; m<=k; m=m+1) 
    C[m] = 0 
    // end for 
    for (j=1; j<=A.size; j=j+1) 
    C[A[j]] = C[A[j]] + 1 
    // end for 
    i=0 
    B = array(1, A.size) 
    for (m=0; m<=k; m=m+1) 
    while (C[m]>0) 
    { 
     B[i] = m 
     i = i+1 
     C[m]=C[m]-1 
    } // end while 
    // end for 
    return B 
}

來源

2016-06-12 itaminul

嗨，你沒有排序......所以沒有必要說穩定或沒有... – Thomas

有現有的編程語言顯示算法比這個假設的語言更清晰。只是說......實際上我想說的是：爲什麼讓我們猜測這個「代碼」實際上做了什麼，而不是給出你想到的排序算法的名稱？或者給我們代碼，我們可以執行，看看它是否甚至排序？ – BitTickler

我不知道自己是怎麼稱呼的，但我們稱之爲「Linearsort」，可能是因爲它按線性時間排序......？我認爲這個算法的更一般的名字是計數排序。 – itaminul

這是一個計數/基數排序與一個將數組從n分類到1的單個字段。將最後一個for循環切換爲1到n會使其不穩定，因爲相同的元素將以相反的順序存儲。

來源

2016-06-12 20:10:55 rcgldr

爲什麼這個算法穩定，我怎麼能使它不穩定？

回答

相關問題