counting sort

解法一

#include <iostream>

using namespace std;

const int INPUT_SIZE = 20;
const int BUCKET_K = 10;

int main()
{
    int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 };
    int CountArr[BUCKET_K] = { 0 };

    cout << "Input: ";
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;


    for (int i=0;i<INPUT_SIZE;i++)
    {
        CountArr[input[i]]++;
    }

    cout << "CountArr: ";
    for ( int i = 0; i < BUCKET_K; i++ )
        cout << CountArr[i] << " ";
    cout << endl;

    int outputindex=0;
    for (int j=0;j<BUCKET_K;j++)
    {
        while (CountArr[j]--){
            input[outputindex++] = j;
        }
    }

    cout << "Output: ";
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;

    return 0;
}

解法二

#include <iostream>
using namespace std;

const int INPUT_SIZE = 20;
const int BUCKET_K = 10;

int main()
{
    int input[INPUT_SIZE] = { 2, 4, 6, 4, 7, 1, 4, 9, 5, 3, 7, 2, 2, 6, 9, 3, 7, 3, 4, 4 };
    int output[INPUT_SIZE] = { 0};
    int CountArr[BUCKET_K] = { 0 };

    cout << "Input: ";
    for (int i = 0; i < INPUT_SIZE; i++ )
    cout << input[i] << " ";
    cout << endl;


    for (int i= 0; i < INPUT_SIZE;i++)
    {
        CountArr[input[i]]++;
    }


    cout << "CountArr:\n";
    for (int i = 0; i < BUCKET_K; i++ )
    cout << CountArr[i] << " ";
    cout << endl;


    for (int i= 1; i < BUCKET_K;i++)
    {
        CountArr[i] += CountArr[i - 1];
    }


    cout << "handled CountArr:\n";
    for (int i = 0; i < BUCKET_K; i++ )
    cout << CountArr[i] << " ";
    cout << endl;


    for (int i= 0; i < INPUT_SIZE;i++)
    {
        output[CountArr[input[i]] - 1] = input[i];
        --CountArr[input[i]];
    }


    cout << "Output: ";
    for (int i = 0; i < INPUT_SIZE; i++ )
    cout << output[i] << " ";
    cout << endl;

    return 0;
}