算法与数据结构之计数排序

计数排序

计数排序是一种稳定的排序算法，它的时间复杂度是O(n+k)，其中，数组元素均≥0，且≤k

计数排序的主要思想就是

①先算出每个元素出现的次数，并且按照元素值为下标，存储在一个临时数组里。

②在上面一步的临时数组内，算出≤x的元素个数（注意，数组下标就是x）

③根据上面的元素值和临时数组内的计数的关系，计算出结果数组。举个例子，临时数组第3位的值为6，那么就是说，结果数组里，下标为6的元素值是3.

这个关系就会有点绕，需要细细理解一下。

理解了上面的思想之后，再往下想一步，就会发现一个问题了：要是待排序的数组里有多个相同元素怎么办？

那么，我们只需要先从原数组的最后一位元素开始处理，然后每次处理完之后，把临时数组对应那个元素的值减1，当再次遇到相同元素的时候，那个元素不就排在上一个相同元素的前面了吗？

这一步也关系到计数排序是否稳定的问题。如果我们从原数组的第0位开始处理，那么相同元素的顺序就会颠倒，从而打破了稳定性。所以，我们需要从原数组的最后一位开始处理。

例题

这里仍然举AIZU Online Judge上的题目，题号是ALDS1_6_A

链接地址：

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_A

题目：

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.

Output

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

Constraints

1 ≤ n ≤ 2,000,000

0 ≤ A[i] ≤ 10,000

Sample Input 1

7
2 5 1 3 2 3 0

Sample Output 1

0 1 2 2 3 3 5

代码实现

#include<iostream>
using namespace std;


int num[2000005], tmp1[2000005]={0}, tmp2[2000005]={0};
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
    }

    for(int i=0;i<n;i++)
        tmp1[num[i]]++;

    for(int i=1;i<=2000000;i++)
        tmp1[i] += tmp1[i-1];

    for(int i=n-1;i>=0;i--)
    {
        tmp2[tmp1[num[i]]] = num[i];
        tmp1[num[i]]--;
    }

    for(int i=1;i<=n;i++)
    {
        cout<<tmp2[i];
        if(i!=n) cout<<" ";
    }
    cout<<endl;
}