Go Through算法导论:计数排序

2016年01月20日 原创
关键词: C++ 数据结构 算法 算法导论
摘要 本文介绍了什么是计数排序以及计数排序的实现方法。

计数排序假设n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为Θ(n)。

计数排序的基本思想是:对每一个输入元素x,确定小于x的元素个数。利用这一信息,就可以直接把x放到它在输出数组中的位置上了。例如,如果有17个元素小于x,则x就应该放在第18个输出位置上。当有几个元素相同时,这一方案要略做修改。因为不能把它们放在同一个输出位置上。在计数排序算法的代码中,假设输入是一个数组A[1..n],A.length=n。我们还需要两个数组:B[1..n]存放排序的输出,C[0..k]提供临时存储空间。

COUNTING-SORT(A,B,k)

  left C[0..k] be a new array

  for i = 0 to k

    C[i] = 0

  for j = 1 to A.length

    C[A[j]] = C[A[j]]+1

//C[i]现在是A中等于i的元素的个数

  for i = 1 to k

    C[i] = C[i] +C[i-1]

//C[i]现在是A中小于或等于i的元素的个数

  for j = A.length downto 1

    B[C[A[j]]] = A[j]

    C[A[j]] = C[A[j]] - 1

下面是该算法的C++代码

#include<iostream>
using namespace std;
void countingsort(int *a, int* b, int n, int k) {
    int* c = new int[k];
    /*memset(c, 0, sizeof(c));*/
    for (int i = 0; i < k; i++) {
        c[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        c[a[i]]++;
    }
    for (int i = 1; i < k; i++) {
        c[i] = c[i] + c[i - 1];
    }
    for (int i = 0; i < n; i++) {
        b[c[a[i]]-1] = a[i];
        c[a[i]]--;
    }
}
int main() {
    int a[10] = { 50, 10, 30, 11, 55, 90, 11, 20, 5, 1 };
    int b[10];
    countingsort(a, b, 10, 100);
    for (int i = 0; i < 10; i++) {
        cout << b[i] << " ";
    }
    cout << endl;
    return 0;
}

运行结果: