設R1，...，RN是n在平面軸對齊矩形的量，角部是在n×n個網格點。因此，對於每個矩形Ri，四個角是其中兩個座標都是{1，...，n}中的整數的點。排序矩形（N）
現在我想這些矩形R1，......通過有增加面積在O（n）的時間Rn的排序。
我有一個算法將它們排序在O（n * log n）中。但是如何在O（n）中完成呢？
使用O（N * log n）的，我們可以這樣做：
Calculate all the areas, and then sort using any standard sorting algorithm like Quick sort
我猜有些每處理將是必需的，這樣我們就可以在O（n）的排序，因爲我們給出了一些可以提供幫助的前提條件。我只想算法，不需要代碼。
由於密鑰的矩形（區域）使用counting sort整數，該任務可以在O(n)的時間內完成。您知道最小密鑰爲0，問題的最大密鑰爲n^2，因此在算法k=n^2+1中。該算法分三步完成：計算直方圖，計算每個鍵的開始和結束索引，然後將數據複製到輸出數組，使用相同的鍵保留輸入的順序，以便排序爲stable。每個傳球是O(n)，因此總共算法是O(n)。
示例：假設n是3 k比，使得所有鍵配合在範圍出現在數據中，最大的鍵一次，[0..k-1]以下，即，k爲10。您通過設置索引從0到k-1的0的數組來創建一個直方圖h，然後通過遍歷矩形集並填充直方圖並對其進行計數。假設有2個區域是1，5個是區域2，2個是區域4. h = [0,2,5,0,2,0,0,0,0,0]。然後立即從直方圖計算出起始索引爲0,0,2,7,7,9,9,9,9,9。任何帶有區域0的矩形都將進入從0開始的輸出數組。任何帶有區域1的矩形都將進入到從0開始的輸出數組（並且在將區域1的矩形放入輸出時增加該數字）。與區2不限矩形進入輸出數組中，以2.任何矩形區域3進入輸出數組以7.如任何矩形區域4進入輸出數組以7.
由於所得區域是整數，您可以實現[基數排序]（http://stackoverflow.com/q/14717560/4856258）算法。 –
@TagirValeev基數排序如何幫助這裏？ – ms8
@python_slayer基數排序是一個[*非比較排序*]（https://en.wikipedia.org/?title=Radix_sort），當k << n時，運行在「O（n）」中細節）。 O（n lg n）下限用於*比較*排序。 – user2864740