如何根據學生的成績排列一系列學生記錄

Question

嘿，我現在正在爲一門考試而學習，而且我似乎無法理解這個概念。 問題是，如果你給出了一系列學生記錄，記錄的成員是學生的名字和他們的成績，那麼你如何按年級對它進行排序。教授給出了他稱之爲「分佈式計數排序」的例子。我無法理解它，並希望有人可以給我的僞代碼或算法下面的代碼， 謝謝:)

Function Distribution_counting_sort(S, n){ 
//Input: a student array S of n records 
//Output: a sorted array (wrt grade) NS 
int count[101]; /*init to 0’s */ 
/* counting */ 
for (i = 0; i < n; i++) count[S[i].grade]++; 
/* accumulating */ 
count[0]--; 
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i]; 
/* distribution */ 
for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i]; 

Answer 1

這實質上的Bucket Sort的變化。

這些桶，每一個可能的等級：

int count[101]; /*init to 0’s */ 

此統計有多少學生每個年級。這告訴我們每個桶的大小：

for (i = 0; i < n; i++) count[S[i].grade]++; 

這將計數轉換爲累計。這給了我們每個桶在目標數組中的結束位置。我相信count[0]--位是爲了解決基於0的陣列。

count[0]--; 
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i]; 

現在，它將每個學生放在他/她的桶的末端，並減少該桶的位置值。

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i]; 

這種排序的好處是它是O（n），而不是O（n * log（n））。然而，它只適用於可以離散化爲有限（且可管理）數量的桶的事物。

這段代碼有點有趣的一件事是，它顛倒了具有相同成績的學生的排序。你可以修改它作爲一個穩定的排序，通過將累積計數改爲桶的開始位置，並在填充NS時遞增它們，或者更容易，在最後一個循環中向後穿過S.

Answer 2

這篇文章排序可能有幫助。

http://www.cs.bu.edu/teaching/cs113/spring-2000/sort/

Answer 3

有101個等級，0 - 100

int count[101]; /*init to 0’s */ 

填充計數[]與總數對於每個等級，例如計數[90] = 4表示4人得到了90％的

for (i = 0; i < n; i++) count[S[i].grade]++; 

接着，轉換那些總計到正在運行的帳簿，即，如果57人得到了比90下，然後計算[90] = 57 + 4，或者61.因此，對於每個計數[n]，您都有這個等級或更低的人數。這對於最終數組非常重要......在最終數組中，需要61個元素來控制每個達到90或更低的元素。需要注意的是計數[100]應該=正傳遞

計數[0] - 被移動整個向下計數被一個，其中基於1的陣列天線的最終轉換到基於0最終陣列，例如如果我有一個人得到一個零，計數[0] = 1，所以我最後的數組將開始在NS [1]。我想從NS [0]開始。因此，上述61個元件，現在是60

count[0]--; 
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i]; 

最後（希望他不要再使用「I」），找到每個等級的地方......如果有60人與「90後」或以下，等級'90'屬於最終陣列的第60個元素NS。這很令人困惑，部分原因是' - '...請記住，'90'級別有60個，所以你來的第一個'90'將被放置在NS [60]，因爲有59個成績較低的人。 '90'的計數減少到59，所以下一個'90'將被放置在NS [59]。等等。

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i]; 

最終的結果是一個最低級到最高等級陣列，其中NS [0]是最低等級，和NS [N]爲最高等級。

有意義嗎？這真是一個漂亮的算法！