题目要求：

　　如何对n个数进行排序，要求时间复杂度O(N).空间复杂度为O(1).

题目分析：

　　严格的说，这道题给出的条件不全。如果这n个数字的大小跨度很大（1~无穷大），则肯定达不到要求。

　　如果n个数字的大小在一定范围内（如0~65535），则可以用hash表的方法。定义为int hash[65536],占用的内存空间固定为sizeof(int)*65536,则空间复杂度为O(1).

　　那么怎么时间复杂度为O(N)呢？即可以遍历几遍数组就可以排序完成。实际上我们可以遍历一遍数组，再遍历一遍hash空间就可以输出排序后的结果。

　　下面举个例子，为了简化起见，假设所有的数字都在0~10之间，则定义int hash[10]，并初始化hash[0~9]=0;

　　令原数组的n个数为:{7,4,3,4,7,2,1,9}.

　　第一遍遍历数组，每次都进行hash[a[i]]++处理,这样结果是hash[7]=2,hash[3]=1....

　　第二遍遍历hash数组，从hash[0]~hash[9]，当hash[i] = x时，连续输出x个i。这样最后输出的结果就是1 2 3 4 4 7 7 9.

　　时间复杂度为O(N).空间复杂度为O(1).done.... 

代码实现：

#include <iostream>using namespace std;const int N = 8;const int HASH_SPACE = 65536;void Sort(int a[],int n,int hash[]);int main(void){    int a[N] = {7,4,3,4,7,2,1,9};    int hash[HASH_SPACE] = {0};    Sort(a,N,hash);    return 0;}void Sort(int a[],int n,int hash[]){    for(int i=0;i<n;i++)    {        hash[a[i]]++;    }    for(int i=0;i<HASH_SPACE;i++)    {        while(hash[i])        {            cout << i << " ";            hash[i]--;        }    }    cout << endl;}

一道看上去很吓人的算法题 【微软面试去100题 第四十九题】