O(n)複雑度の並べ替えアルゴリズム

ツールバーの
並べ替えのアルゴリズムは多く,またそれぞれ優劣がある.入力データの範囲が既知であり、データ分布が均一である場合、以下で説明するアルゴリズムは比較的有効である.1つの配列には2つの情報があり、格納された値とインデックスに値するものがあり、時には値を格納するために使用されるだけで、他の情報は無駄になります.
構想
インデックス自体が順序を表すことができるので,それを利用してソートを簡略化するのも当然である.もし我々が入力データの範囲が0~99であれば,入力データの規模Nは知らない.範囲は100しかないので、100個の要素の配列を作成するだけで、対応するインデックス記録要素が現れる回数を排除することができます(以下のコードはc++11仕様を使用します).以上の例では、vectorvec{13,34,25,78,34,25,39,67,25,12,13}をソートします.int book 100を作成します.

for(int i = 0; i <vec.size(); ++i)
    book[vec(i)] += 1;

最後の出力は,対応する値が何であるかを数回出力する.だから

for(int i =0 ; i < 100; ++i)
{
    for(int j = 0; j < vec[i]; ++j )
        cout << i << " ";
}

    12， 13，13，25，25，25，34，34，39，67，78.           。              。

sort.cpp：
#include 
/*
 *input          
 *N            ，M      
 *        
 */
template <class T>
T* sort(T* input, int N, int M)
{
  T* output = new T[M]();
  for (int i = 0; i < N; i++)
      output[input[i]] += 1;
  return output;
}
//   main    
int main()
{
  int input[10] = {23, 25, 24, 67, 34, 23, 67, 94,25, 23};
  int* output = sort(input, 10, 100);
  for(int i = 0; i < 100; i++)
    {
        for (int j = 0; j < output[i]; ++j)
            std::cout << i << " ";
    }
  return 0;
}