用於比較計數算法的僞代碼

我正在爲我的算法類做家庭作業問題，而且我對這個特定算法的工作原理感到驚歎。我已經在網上找到了答案，所以我不在尋找答案，只是一些幫助逐步完成代碼。根據我目前所瞭解的情況，該算法接受未指定長度的數組，並通過多次迭代，通過比較數組中單個元素與較小元素來對數字進行排序。在迭代結束時，它爲每個元素指定一個位置索引，該位置索引指定元素應按非遞減順序排列的順序。但是我無法弄清楚第一個循環完成後第二個待辦事項循環如何從迭代開始？任何幫助將不勝感激用於比較計數算法的僞代碼

問題：考慮對於排序由計數陣列，對於每個其元素，更小的元件的數量的排序問題的算法，然後使用此信息來把元件在它在排序數組中的適當位置。排序號碼，以下列表（60，35，81，98，14，47）：

Algorithm ComparisonCountingSort(A[0..n − 1], S[0..n − 1]) 
//Sorts an array by comparison counting 
//Input: Array A[0..n − 1] of orderable values 
//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order 

for i ← 0 to n − 1 do 
    Count[i] ← 0 

for i ← 0 to n − 2 do 
    for j ← i + 1 to n − 1 do 
      if A[i] < A[j] 
       Count[j] ← Count[j] + 1 
      else 
       Count[i] ← Count[i] + 1 

for i ← 0 to n − 1 do 
    S[Count[i]] ← A[i] 

return S

來源

2014-09-19 user2827137

你能更好地格式化代碼嗎？如果縮進是合適的，則不需要括號，但目前我無法確定這些是嵌套的還是什麼。 – Compass 2014-09-19 21:02:32

@Compass，我希望有幫助，謝謝 – user2827137 2014-09-19 21:07:50

第一個循環在第一個循環完成後不會啓動，第二個循環的第一個實際上是嵌套**到第一個循環。 – Fallen 2014-09-19 21:12:43

這個排序算法的關鍵是認識到如果一個數x陣列中具有完全相同n元件該數組較小，然後在排序數組中它應該是n'th元素（在零索引數組中）。

那麼算法想要做的是檢查每個元素還有多少其他元素更小。但是你最終會檢查每一對兩次，這是不必要的。第二個循環是以這樣一種方式構建的，即每一對都被精確比較一次。

第二環路，其爲雙for循環中，可以顯現如下的情況，其中長度N是4：

1st outer loop | i -> [0] 
       | j -> [1] [2] [3] 

2nd outer loop | i -> [1] 
       | j -> [2] [3] 

3rd outer loop | i -> [2] 
       | j -> [3]

這裏i和j是你的循環迭代器和托架之間的值是他們採取的指數的價值。現在你可以清楚地看到，每一對都用這種結構進行比較一次

來源

2014-09-19 21:34:21 Pankrates

這實際上有幫助，但如果沒有太多的麻煩，你可能會讓我開始名單上的{60,35,81,98,14 ，47}？我甚至不知道從哪裏開始 – user2827137 2014-09-19 22:07:46

你是什麼意思讓你開始？你說你有代碼，它的工作 – Pankrates 2014-09-19 22:18:57

它被提供給我們作爲一個家庭作業問題，我有解決方案，我在網上找到，但我想弄清楚如何將算法實際應用到列表中，所以我在尋求如何開始迭代的幫助，一旦我知道如何做，我可以找出我的其餘部分自己的 – user2827137 2014-09-19 22:23:53

感謝您給予的任何幫助，但是我在工作了一段時間後才弄清楚了。從外行的角度來說，你從第一列開始，它是當前的第一列，並將它與它後面的每一列進行比較（這將是比較中的j），如果我大於j，那麼我得到1。 j得到1.在第一行由全零組成之後，第二行被迭代。使用60作爲我，你將它與當前j的35進行比較，因爲60大於35，60得到1（如果你願意的話，會計數）。然後你比較60到81，因爲這成爲新的j。由於81高於60，所以81得到理貨標記。這一直持續到行的其餘部分完成。在下一次迭代中，下一列變成新的i，並且下一個將逐個變成新的j。沖洗並重復，直到所有的行和列都完成，並且每個元素都有一個新的索引值，然後按順序排列。

來源

2014-09-20 02:11:36 user2827137

用於比較計數算法的僞代碼

回答

相關問題