超级经典的计数排序算法，号称效率达到了O(n)

#include <string> #include <iostream> #include "CountingSort.h" //这个头文件主要是为了计算一个数组中的最大值。 #include "../../Max.cpp" template <class T> CountingSort<T>::CountingSort(){ m_resultArrayPtr = NULL; } template <class T> CountingSort<T>::~CountingSort(){ delete [] m_resultArrayPtr; } template <class T> bool CountingSort<T>::Sort(T* needSortArrayPtr,long length){ if( length < 1 ) return false; if(_FindMax(needSortArrayPtr,length)!=true) return false; //之所以有这个判断是因为，计数排序的前提是数据集必须为正整数， //因此，如果最大值为负时，则数据集一定不全为正， if(m_max < 0) return false; long numberLineCount(0); numberLineCount = static_cast<long>(m_max); // “数轴”,用于存放数据集中每个数值出现的频率 T *numberLinePtr = new T[numberLineCount]; memset(numberLinePtr,0,numberLineCount*sizeof(T)); long index(0); for(int i= 0;i<length;i++){ index = static_cast<long>(*(needSortArrayPtr+i)); ++ (*(numberLinePtr+index-1)); } //计算出数据集中每个数值在位置，注意：这里是理解这个非比较算法的重点， for(int i=1;i<numberLineCount;i++){ (*(numberLinePtr+i)) += (*(numberLinePtr+i-1)); } m_resultArrayPtr = new T[length]; memset(m_resultArrayPtr,0,length*sizeof(T)); for(int i=0;i < length;i++){ //这里先用拿到数据集中的一个数值 index = static_cast<long>(*(needSortArrayPtr+i)); //由这个数值作为索引去取这个数值的位置 //问：”数轴“为什么不会越界呢？ //答：之前我们new这个”数轴“的时候是以整个数据集中的最大值来创建的。 index = static_cast<long>(*(numberLinePtr+index - 1)); //由位置直接插入。 *(m_resultArrayPtr+index-1) = static_cast<long>(*(needSortArrayPtr+i)); //这一步是必须的，如果数据集中有相同的数值时，必须减1。 --(*(numberLinePtr+*(needSortArrayPtr+i) - 1)); } delete [] numberLinePtr; return true; } template <class T> T* CountingSort<T>::GetResult(){ if(m_resultArrayPtr!=NULL) return m_resultArrayPtr; } template <class T> bool CountingSort<T>::_FindMax(T* needSortArrayPtr,long length){ Max<T> max; m_max = max.GetMax(needSortArrayPtr,length); return true; }