排序十億學生

Question

在每個面試問題，我一直在問「你會如何排序的十億學生名單，根據他們的測試總成績？從1-學生的舉動卷數的列表1B和分數的範圍是10-100。「 雖然任何排序算法會做，但效率高嗎？

Answer 1

只需運行counting sort輸入，它在這種情況下O(n)，因爲範圍爲界。這也是最有效的方式，因爲任何輸出所有學生的方法都需要Ω（n）。

您可以通過他們的循環可能獲得分數輸出的學生（例如，如果90個可能的分數存在，通過學生圈90倍，在第一時間輸出學生的分數100，....）。

這個任務可以通過bucket sort完成。但首先你應該循環輸入，找到每個相關學生的分數，然後通過考慮其學生數量爲每個分數創建一個桶，然後填充桶，注意你應該創建一個桶的數組，也應該有一個額外的參數，用於在每個存儲桶中保存當前項目數第一種方法（使用直接計數排序）是O（n），O（1）額外空間，第二種方法是O（n），O（n）多餘空間，但第二種方法更快，因爲它是2*n，第一個是90*n。

Answer 2

使用計數排序。如果你知道在這個問題中滿足的最大值和一些其他參數，那是很好的。它在排序爲O（n）

Answer 3

我會用某種鴻溝而治之算法（如合併排序或快速排序或桶排序），並使用這個想法告訴了幾個桶之間進行劃分排序。 當您需要將所有數據合併回大數組時，會出現問題，但由於子數組已經排序，只需要O（n）。

bucket sort(L) 
{ 
list Y[k+1] 
for (i = 0; i <= k; i++) Y[i] = empty 
while L nonempty 
{ 
    let X = first record in L 
    move X to Y[key(X)] 
} 
for (i = 0; i <= k; i++) 
concatenate Y[i] onto end of L 
} 

有兩個循環取O（k）時間，一個取O（n），所以總時間爲O（n + k）。當k小於n時這是好的。例如。假設你想按分數排序10億人; n = 1000000000，k = 100-10，所以時間= O（n）。