满足适当条件的O(n)排序算法

   前天去面试某互联网公司的时候，碰到了一道排序算法题，要求时间复杂度为O(n)，即使快速排序算法时间复杂度也为O(nlogn)，紧张情况下也没想到好办法。只好说暂时想不到，回家在看看。

   题目大概是这样子：有N个正整数序列，数值范围在1到1000000，要求对该序列进行排序，时间复杂度为O(n)。

   回来重新看了看题目，发现“数值范围在1到1000000”这个前提条件非常重要，决定了时间复杂度是否可以为O(n)的问题。其实有个限制，我们就可以那数组来做文章了，简单就可以实现了，算法实现如下。

#define MAX_VALUE (10000000)
unsigned int base[MAX_VALUE+1]={0};
#define N (10000)
unsigned int array[N];
void integer_sort(unsigned int a[],int nLen)
{
    int i;
    int k;
    int j=0;
    for(i = 0;i < nLen;i++)
    {
        base[a[i]] += 1;  //o(n)
    }

    for(i = 1; i <= MAX_VALUE;i++)
    {
        k = base[i];
        for(;k>0;k--){
            array[j++] = i;//o(n)
        }
    }
}