如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)
------------------------------------------
熟悉排序算法的人知道，目前比较好的排序算法就是快排堆排序归并等等，这些算法也只能让时间复杂度在O(NlogN)
但是这道题却想让时间复杂度达到O(N)这个真心要想破我的头了。。
刚开始思路是，可以不可以用哈希来排序，因为这个家伙太好用了，就是一个萝卜一个坑，非常方便，可是我误解了这里空间复杂度，O(1)只是表示额外空间是一个常量，与n无关，所以确实可以用Hash来排序
给的是n个整数，所以我们可以申请一个int hashTable[65535]
循环遍历给定数组，分别在hashTable[arr[i]]++。这样，这个hash表不仅记录了该元素存在，同时记录来它的个数
第二次遍历，只需要按照从小到大的顺序取出结果，注意元素个数即可。
当然，如果大家心疼计算机内存，可以先遍历一次给定数组，记录最大元素，然后根据这个最大量来申请哈希表大小
还有这里如果有负数来怎么办？这个问题大家可以考虑下，当然可以申请2*65535个空间，一半装负，另一半装正
对我这个从不惜疼内存的人来说，再大都申请～
代码如下
//============================================================================
// Name : SuperSort.cpp
// Author : YLF
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
void SuperSort(int *arr, int n);
int main() {
int n;
cin>>n;
int i = 0;
int *arr = new int[n];
for(i=0;i<n;i++)
cin>>arr[i];
SuperSort(arr,n);
//前面几个实验都老是忘了delete 这个很不好，还是要铭记在心，尤其我是那么那么的珍惜内存啊
delete arr;
return 0;
}
void SuperSort(int *arr, int n){
int hashTable[65535];
int i = 0;
//申请空间初始化
for(i=0;i<65535;i++)
hashTable[i]=0;
//排序
for(i=0;i<n;i++)
hashTable[arr[i]]++;
//结果
for(i=0;i<65535;i++){
if(hashTable[i] != 0){
cout<<i<<" ";
hashTable[i--]--;
}
}
}
10 2 5 7 8 0 4 3 2 1 3 7 0 1 2 2 3 3 4 5 7 8