计算机里有一种算法----计数，这个算法有很多使用的价值，比如说我们可以通过计数算法统计每个字符出现的分布图， 计数也是统计里面的一个基本步骤。

计数排序就是一种类似求元素的分布图的一种算法。
计数排序的要求如下：

1. 元素必须是可以进行类似数组的分布，而且这种分布的区域不应该太大。（这点很重要）
2. 元素是可以计数的

上面的要求1是个核心的要求，比如，如果我要排序“1， 10001， 100”， 针对这个序列我们需要一个10001的大的分布空间，用来统计每个元素出现的次数。这个空间的换取可能不值当。因为我们还必须对统计空间进行一次统计求和，统计求和的基数就是统计空间的大小。

基数排序是一种稳定的排序，也就是说如果排序的元素值是相等的，元素还保持原有序列中的顺序，这个特性是基数排序的基础。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> CountSort(const vector<int> & vecNum)
{
    vector<int> vecNumSort;

    if (vecNum.empty()) return vecNumSort;

    vector<int> vecCount;
    int nJizhi = 0;
    int nSize  = 0;
    int nMax   = vecNum[0];
    int nMin   = vecNum[0];
    for (auto itr=vecNum.begin();
          itr!=vecNum.end();
          ++itr)
    {
        if (nMax < *itr) nMax = *itr;
        if (nMin > *itr) nMin = *itr;
    }

    nJizhi = nMin;
    nSize  = nMax - nMin + 1;

    vecCount.assign(nSize, 0);
    for (auto itr=vecNum.begin();
          itr!=vecNum.end();
          ++itr)
    {
        vecCount[*itr-nJizhi] += 1; 
    }

    for (int i=1; i<vecCount.size(); ++i)
    {
        vecCount[i] = vecCount[i] + vecCount[i-1];
    }

        // 保持稳定
    vecNumSort.resize(vecNum.size());
    for (auto itr=vecNum.rbegin();
          itr!=vecNum.rend();
          ++itr)
    {
        vecNumSort[vecCount[*itr-nJizhi]-1] = *itr;
        vecCount[*itr-nJizhi] -= 1;
    }

    return vecNumSort;
}

void Output(int a)
{
    cout << a << " ";
}

int main(int argc, char ** argv)
{
    const int LEN = 8;
    int a[LEN] = {2, 5, 3, 1, 2, 3, 1, 3};
    vector<int> vecNum(a, a+LEN);
    for_each(vecNum.begin(), vecNum.end(), Output);
    cout << endl;
    vecNum = CountSort(vecNum);
    for_each(vecNum.begin(), vecNum.end(), Output);
    cout << endl;
    return 0;
}