一道看上去很嚇人的算法面試題：如何對n個數(shù)進(jìn)行排序，要求時間復(fù)雜度O(n)，空間復(fù)雜度O(1)看上去似乎任何已知的算法都無法做到，如果誰做到了，那么所有的排序方
法：QuickSort，ShellSort，HeapSort，BubbleSort等等等等，都可以扔掉了，還要這些算法干嗎阿，呵呵。不過實際上，
在數(shù)字范圍有限制的情況下，是有一個這樣的算法的，只需要用一個數(shù)組記錄每個數(shù)字出現(xiàn)次數(shù)就可以了。
假定你的數(shù)字范圍在0到65535范圍之內(nèi)，定義一個數(shù)組count[65536]（這個空間是常量，和n無關(guān)，所以是O(1) )，初值全部為0。
那么假設(shè)有下面這些數(shù)字：
100
200
300
119
0
6
...
那么對于每個這個數(shù)字，都做在count中記錄一下：
100 => count[100]++
200 => count[200]++
300 => count[300]++
119 => count[119]++
0 => count[0]++
6 => count[6]++
...
最后，遍歷一邊所有這些數(shù)字就可得到0~65535每個數(shù)字的個數(shù)（在count數(shù)組中），然后再順序遍歷count數(shù)組，count[n] =
m，則輸出m個n，（比如說有count[3] = 2,
那么說明有2個數(shù)字3），依次輸出，最后可得結(jié)果。第一次遍歷是O(n)，第二次遍歷是O(1)，為常量，所以最后的時間復(fù)雜度為O(n)，而空間復(fù)雜度
為O(1)
這個算法很簡單，相信大家都會，只是這個題太過于變態(tài)了，一般會把面試者嚇?。ㄎ以瓉砻嬖囈渤鲞^這個題，只不過題目的表述形式要“友善”的多，呵呵）
|
|
|
