#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;
}
