计数排序算法

参考： 计数排序算法

特性：

只用于无符号整数，对于有符号的整数可以通过对每个数组元素都加减一个数解决。
通过计算数组元素的最大、最小值得到统计数组的大小
需要使用额外的空间，空间大小是(元素的最大值-元素的最小值)
当待排序数组内有大量重复的数值时使用计数排序算法较有优势
时间复杂度是max( O(元素的最大值-元素的最小值), O(n) )
空间复杂度是max( O(元素的最大值-元素的最小值), O(n) )

#include <iostream>
#include <vector>
#include <time.h>

typedef std::vector<size_t> TIntArray;
static void display(const TIntArray& vecValue)
{
 for( size_t i = 0; i < vecValue.size(); ++i )
 {
  if( i != 0 && (i % 10) == 0 )
   std::cout << std::endl;
  std::cout << vecValue[i] << " ";
 }
 std::cout << std::endl;
}

class TCountSort
{
public:
 static void setMaxBound(size_t nMaxBound) { g_nMaxBound = nMaxBound; }

 bool countSort(TIntArray& vecValue)
 {
  size_t nSize = vecValue.size();
  if( nSize <= 0 )
   return false;

  size_t nMinValue = vecValue[0], nMaxValue = vecValue[0];
  getMinMaxValue(vecValue, nMinValue, nMaxValue);

  size_t nBound = nMaxValue - nMinValue + 1;
  if( nBound > g_nMaxBound )
   return false;

  resetEnv(nSize, nBound);
  size_t i = 0;
  //统计每个数出现的次数
  for( i = 0; i < nSize; ++i )
   ++m_vecStat[vecValue[i] - nMinValue];
  for( i = 1; i < nBound; ++i )
   m_vecStat[i] += m_vecStat[i-1];

  //根据统计数组将原数组排序到m_vecSwap
  for( i = nSize - 1; i >= 0 && i < nSize; --i )
  {
   m_vecSwap[m_vecStat[vecValue[i]-nMinValue] - 1] = vecValue[i];
   --m_vecStat[vecValue[i]-nMinValue];
  }
  vecValue.swap(m_vecSwap);
  return true;
 }

private:
 static size_t g_nMaxBound;
 TIntArray m_vecSwap;
 TIntArray m_vecStat;

 void resetEnv(size_t nSortArraySize, size_t nBound)
 {
  m_vecSwap.resize(nSortArraySize);
  m_vecStat.resize(nBound);
  for( size_t i = 0; i < nBound; ++i )
   m_vecStat[i] = 0;
 }
 
 void getMinMaxValue(const TIntArray& vecValue, size_t& nMinValue, size_t& nMaxValue)
 {
  nMinValue = vecValue[0];
  nMaxValue = vecValue[0];
  for( size_t i = 1; i < vecValue.size(); ++i )
  {
   if( nMinValue > vecValue[i] )
    nMinValue = vecValue[i];
   if( nMaxValue < vecValue[i] )
    nMaxValue = vecValue[i];
  }
 }
};

size_t TCountSort::g_nMaxBound = 1024 * 1024;

void initSrcArray(TIntArray& vecValue, size_t nCount)
{
 size_t t = static_cast<size_t>( time(NULL) );
 for(size_t i = 0; i < nCount; ++i )
  vecValue.push_back( ((t+ i + 3) * (t+ i + 11)) % 10 );
}

void testCountSort()
{
 TIntArray vecValue;
 initSrcArray(vecValue, 10);

 std::cout << "排序前为:" << std::endl;
 display(vecValue);

 TCountSort countSort;
 countSort.countSort(vecValue);
 std::cout << "排序后为:" << std::endl;
 display(vecValue);
}