【ソートアルゴリズム】:カウントソート

構想:並べ替えられた配列をAとし,並べ替え後Bに格納し,Cを一時配列とする.カウントとは、まず1つの配列C[i]によってiに等しい大きさの要素の個数を計算し、この過程は1回の循環遍歴だけでよい.これに基づいて,i以下の要素個数を計算することも,一重ループで完了する.次のステップは、length[A]から1までの逆順サイクルで、A[i]をBのC[A[i]]番目の位置に配置します.原理は:C[A[i]]はa[i]以下の要素の個数を表し、ちょうどA[i]がソートされた後にあるべき位置である.またlength[A]から1逆シーケンスサイクルまでは,同じ要素間の相対順序が変わらないことが保証され,これもカウントソート安定性の体現である.配列Aにアクセサリ属性がある場合,安定性は非常に重要である.実は上のbbはそんなに多くて、道理はとても簡単で、1つのrangの大きさの配列を開いて、rangの範囲は配列の要素の大きさの範囲です.そして並べ替え配列に基づいて新しく開いた配列を位置++に対応させる.そしてもう一度読みます.
コード:

void CountSort(int* arr, int len)
{
    assert(arr);
    assert(len > 0);

    int min = arr[0];
    int max = arr[0];

    for (int i = 1; i < len; i++)
    {
        if (arr[i]>max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }

    int range = max - min + 1;
    int* counts = new int(range);
    memset(counts, 0, sizeof(int)*range);

    for (int i = 0; i < len; i++)
    {
        counts[arr[i] - min]++;
    }

    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (counts[i]--)
            arr[j++] = i + min;
    }
}