算法数据结构C++实现4-计数排序(counting sort) - c++编程基础

这里是 Introduction to Algorithm 算法导论书中第八章的计数排序 counting sort，本专题还是以这本书为主，用c++实现其中最重要的算法。

网上也有很多高手研究了这本书，给出了读书摘要；但是先要深入学习这本书的话，还是需要自己去看书的。本专题的特色就是直接给出程序实现；

这本书的算法还是非常简明易懂的，就是算法分析和一些数学问题会比较难，这些内容还是需要有时间自己慢慢研究的，不过有些比较深入的内容的话，工作中用的会比较少，所以这里主要实现其中的算法。

下面是计数排序 counting sort 的全部代码。

#include  
#include  
#include  
using namespace std;  
  
void countingSort(vector &ib, vector &ia, int maxEle)  
{  
    vector ic;//new vector[11]; 这里用new会出现下标溢出的错误!!!  
    int i = 0;  
    ic.resize(maxEle+1,0);//注意这是正确的单个vector分配空间的正确用法!!!  
  
    for(auto x:ia)  
    {  
        ic[x]++;  
    }  
  
    for(i=1; i<=maxEle; i++)  
    {  
        ic[i]=ic[i]+ic[i-1];  
    }  
  
    for(i=ia.size()-1; i>=0; i--)  
    {  
        ib[ic[ia[i]]-1]=ia[i];  
        ic[ia[i]]--;  
    }  
}  
  
void countingSort(vector




 &ia, int maxEle)  
{  
    vector ib(ia);  
    countingSort(ia,ib,maxEle);  
}  
  
template  
class Print  
{  
public:  
    Print(){}  
    void inline operator()(const T& x) const{cout< vecI1(a,a+4);  
        vector vecI11(4);  
        int b[7]={2,10,7,10,9,4,5};  
        vector vecI2(b,b+7);  
        vector vecI22(7);  
  
        countingSort(vecI1,9);  
        countingSort(vecI2,10);  
  
        for(auto x:vecI1)  
        {//C++11标准遍历数组，非常方便  
            cout<());  
        cout<

重点还是要注意下标的问题，和vector的用法，vector分配内存问题。算法并不难实现。