count_sort.cpp

闲着无事写的一个count_sort的程序和大家一起分享

//count_sort by suqiang @ neuq & jlu 更详细的内容请访问：http://blog.csdn.net/china8848

#include <memory>
#include <iostream>
using namespace std;
#define MAX_SIZE 1000  //数组大小
#define MAX_NUM 1000    //数组中最大值
int main()
{    
    int A[MAX_SIZE],i,n=10;
    for(i=1;i<=n;i++)
        A[i]=n-i+1;

    //计数排序，A[]为初始数组，下标从1开始，B[]为结果数组，下标从1开始,C[]为辅助数组
    int C[MAX_NUM],max_element=0;
    int B[MAX_SIZE],temp;
    memset(C,0,4*MAX_NUM);
    for(i=1;i<=n;i++)
    {
        temp=A[i];
        if(temp>max_element)
            max_element=temp;
        C[temp]++;
    }
    for(i=0;i<=max_element;i++)
        C[i+1]+=C[i];

    for(i=n;i>=1;i--)
    {
        B[C[A[i]]]=A[i];
        C[A[i]]--;
    }


    for(i=1;i<=n;i++)
        cout<<B[i]<<endl;
    return 1;
}