Aizu-ALDS1_6_A Counting Sort¶

Description¶

Counting sort can be used for sorting elements in an array which each of the n input elements is an integer in the range 0 to k. The idea of counting sort is to determine, for each input element x, the number of elements less than x as C[x]. This information can be used to place element x directly into its position in the output array B. This scheme must be modified to handle the situation in which several elements have the same value. Please see the following pseudocode for the detail:

Counting-Sort(A, B, k)
1    for i = 0 to k
2        do C[i] = 0
3    for j = 1 to length[A]
4        do C[A[j]] = C[A[j]]+1
5    /* C[i] now contains the number of elements equal to i */
6    for i = 1 to k
7    do C[i] = C[i] + C[i-1]
8    /* C[i] now contains the number of elements less than or equal to i */
9    for j = length[A] downto 1
10       do B[C[A[j]]] = A[j]
11          C[A[j]] = C[A[j]]-1

Write a program which sorts elements of given array ascending order based on the counting sort.

Input¶

The first line of the input includes an integer n, the number of elements in the sequence.

In the second line, n elements of the sequence are given separated by spaces characters.

Constraints¶

1 ≤ n ≤ 2,000,000
0 ≤ A[i] ≤ 10,000

Output¶

Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

Sample Input¶

7
2 5 1 3 2 3 0

Sample Output¶

0 1 2 2 3 3 5

#include <bits/stdc++.h>

using namespace std;

vector<int> tmp(10005, 0);
vector<int> seq(2 * 1e6 + 5), help(2 * 1e6 + 5);
int n, maxNum = 0;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (int i = 1; i <= n; ++i) {
        os << v[i];
        if (i != n) os << ' ';
    }
    os << endl;
    return os;
}

void countingSort()
{
    //统计每个数字出现的次数
    for (int i = 0; i < n; ++i) ++tmp[seq[i]];

    //统计小于等于i的数字的个数
    for (int i = 1; i <= maxNum; ++i) tmp[i] += tmp[i - 1];

    //数值写入排序后的数组help,倒序保证稳定性
    for (int i = n - 1; i >= 0; --i) {
        help[tmp[seq[i]]] = seq[i];
        --tmp[seq[i]];
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> seq[i];
        maxNum = max(maxNum, seq[i]);
    }
    countingSort();
    cout << help;

    return 0;
}