Counting Sort

counting_sort.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

/*
 *  计数排序    O(n)
 *  假定输入元素为在0-k之间的整数
 */
void counting_sort(int a[], int l, int r, int k)
{
	int n=r-l+1;
	int ret[n+1];
	int c[k+1];
	for(int i=0;i<k+1;i++) c[i]=0;
	for(int i=l;i<=r;i++) c[a[i]]+=1;
	for(int i=1;i<k+1;i++) c[i]+=c[i-1];

	for( int i=r;i>=l;i--)  // c[i]中保存了≤i的元素的个数，这样c[a[i]]也就是a[i]排序后的位置
	{
		if(c[a[i]]>0) {
			ret[c[a[i]]]=a[i];
			c[a[i]]--;
		}
	}

	int j=l;
	for(int i=l;i<=r;i++)
		a[i]=ret[j++];
}

int main()
{
	int i;
	int a[10]={2,10,3,9,23,200,2,10,-2222,20};
	counting_sort(a, 0, 9, 2223);
	for(i=0;i<10;i++) cout<<a[i]<<" ";cout<<endl;
}