复杂度为O（n）的排序方法

特殊情况下，排序其实可以做到O（n）的复杂度哦，请看如下例题和说明，这种排序的应用十分广泛，而且速度快，缺点就是需要用空间来换时间

 1 /*
问题描述：如何对公司所有员工的年龄进行排序呢？公司有几万名员工，要求时间复杂度为O(n)
解题思路：总体思路是“用时间换空间”这样的问题一般有这样的特点 
          1、数字有一定的范围，如本次的年龄，范围假设为0-99
          2、数字一定要为整数，因为一个数组的元素是另一个数组的下标
          3、允许的空间复杂度为O(n)；
这种排序方法叫“bucket sort”
*/

void SortAges(int ages[], int length)
{
    if (ages == nullptr || length <= 0)
        return;
    const int theOldestAge = 99;
    int timesOfAges[theOldestAge + 1] = { 0 };
    for (int i = 0; i < length; i++)
    {
        if (ages[i] >= 0 && ages[i] <= 99)
            timesOfAges[ages[i]]++;
        else
            throw new std::exception("out og range");
    }
    int index = 0; //技术变量可以不参与循环体，妙哉
    for (int i = 0; i <= theOldestAge; i++)
    {
        for (int j = 0; j < timesOfAges[i]; j++)
        {
            ages[index] = i;
            index++;
        }
    }
}
int main(int argc, char* argv[])
{
    const int numOfWorkers = 1000;
    int ageOfWorkers[numOfWorkers];
    srand((unsigned)time(NULL));
    for (int i = 0; i < numOfWorkers; i++)
        ageOfWorkers[i] = rand() % 100;
    cout << "ages:" << endl;
    for (int i = 0; i < numOfWorkers; i++)
    {
        cout << ageOfWorkers[i] << " ";
        if ((i + 1) % 5 == 0)
            cout << endl;
    }
    SortAges(ageOfWorkers, numOfWorkers);
    cout << "sorted ages:" << endl;
    for (int i = 0; i < numOfWorkers; i++)
    {
        cout << ageOfWorkers[i] << " ";
        if ((i + 1) % 5 == 0)
            cout << endl;
    }
    system("pause");
    return 0;
}