计数排序算法
参考： 计数排序算法特性：
只用于无符号整数，对于有符号的整数可以通过对每个数组元素都加减一个数解决。
通过计算数组元素的最大、最小值得到统计数组的大小
需要使用额外的空间，空间大小是(元素的最大值-元素的最小值)
当待排序数组内有大量重复的数值时使用计数排序算法较有优势
时间复杂度是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 << " "; } 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, nMaxValue = vecValue;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 - nMinValue];for( i = 1; i < nBound; ++i ) m_vecStat += m_vecStat;//根据统计数组将原数组排序到m_vecSwapfor( i = nSize - 1; i >= 0 && i < nSize; --i ){ m_vecSwap-nMinValue] - 1] = vecValue; --m_vecStat-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 = 0; }void getMinMaxValue(const TIntArray& vecValue, size_t& nMinValue, size_t& nMaxValue) {nMinValue = vecValue;nMaxValue = vecValue;for( size_t i = 1; i < vecValue.size(); ++i ){ if( nMinValue > vecValue ) nMinValue = vecValue; if( nMaxValue < vecValue ) nMaxValue = vecValue;} }};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);}
页:
[1]