算法：分而治之（應用快速排序？！）

Question

有關如何處理下面問題的任何幫助，我們將不勝感激。我也發佈了一些關於這個問題的想法。

你是一個招收n名學生的班級的助教。您有 他們的最終成績（未排序），並且您必須爲他們指定一個可用成績（A，B，C等）。約束條件（假設n是 多的G）：

• 究竟（N/G）學生獲得每個等級（對於 例如，如果n = 30，以及G = {A，B，C} ，那麼正好10名學生獲得A， 10 GET B和10獲得C）
• 較低分數的學生沒有得到一個 更高檔次比具有較高分數（但是學生，他們可能會 相同年級）假設每個學生獲得不同的分數， 導出了一個有效的算法，並根據n 和G給出其複雜度。首先對分數進行排序的任何算法都將接收z ero credit。

我的回答： 好了，問題的最後一行說，我也不好，如果我嘗試了數組排序第一和劃分陣列爲G等份。當使用最佳排序算法時，這將花費O（n log n）。所以，我想到了一個複雜的解決方案。我認爲這個問題是一個快速排序可以派上用場的例子，因爲我們不需要對同一年級的學生進行排序，我們可以有k個關鍵元素，關鍵元素都是等距的。 但是，我們沒有得到學生的評分，我們也被告知每個學生都有不同的分數。

首先，我使用MaxMin分而治之算法計算最大和最小分數，這將花費O（n）時間。使用最大值和最小值，我們可以通過計算大致找出每個等級的關鍵要素。 （最大 - 最小）/ k =最小等級，2 *（最大 - 最小）/ k =第二最低等級。和k-1 *（最大 - 最小）/ k =最高等級。

現在使用這些作爲關鍵元素，我們可以只執行快速排序的分區方法，第一次需要n個時間量，n-（最大 - 最小）/ k第二次，等等。所以算法的時間複雜度爲O（n），因爲min-max問題的複雜度爲O（n），而Quick Sort中的Partition的複雜度爲O（n）。

請分享您的想法。

Answer 1

您可以將所有分數放在（最大）優先級隊列中，然後從中提取n/G組。這仍然是一個隱含的排序，但仍然不被規則所禁止。

Answer 2

這基本上是一個選擇問題，只是你一次做G選擇。

http://en.wikipedia.org/wiki/Quickselect算法的修改應該在這裏工作。儘管Quicksort總是遞歸地下降到兩個分區，並且原始Quickselect僅下降到包含第k個索引的那個分區，但是該問題的算法應當下降到分區當且僅當它包含n/G,2*n/G,(G-1)*n/G數組中的一個索引 - 分級之間的分數。

這些索引是等級之間的分裂點，所以最終得到的是一個數組，其中分裂點之間的元素不一定是排序的，但是這些點之間的塊是。