参考:
计数排序算法
特性:
只用于无符号整数,对于有符号的整数可以通过对每个数组元素都加减一个数解决。
通过计算数组元素的最大、最小值得到统计数组的大小
需要使用额外的空间,空间大小是(元素的最大值-元素的最小值)
当待排序数组内有大量重复的数值时使用计数排序算法较有优势
时间复杂度是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);
}
分享到:
相关推荐
超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称...
countingSort 方法实现了计数排序算法。首先,我们遍历一遍原数组,找出其中的最大值,以确定计数数组的大小。然后,创建计数数组 count,并将每个元素的出现次数记录在计数数组中。接下来,根据计数数组中的元素...
算法导论上计数排序算法的vc.60Test实例
JavaScript计数排序算法计数排序算法计数排序(Counting sort)是一种稳定的线性时间排序算法。计数排序使用一个额外的数组,数组的下标对应待排序
关于计数排序算法 当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。 由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待...
基于python的计数排序算法设计与实现
以前看过网上的一篇关于一种号称时间复杂度能达到O(n)的不用比较就可以实现排序的算法——计数排序法,这是自己用C写的一个实现,大家可以参考下,欢迎指证。
排序算法之计数排序,计数排序是一种线性的排序算法,比基于比较的排序算法效率高,但其应用有特定的领域。我给出了两种策略的计数排序算法,欢迎下载~~如程序中有Bug,恳请指正!
计数排序的代码实现,对应分析在我的博客里找,学习和开发的随便下
提出了一种改进的计数排序算法。首先找到待排序记录应该存放的位置,然后在原数组空间上进行交换。与传统的计数排序算法相比,在不改变时间复杂度的同时,降低了空间复杂度,提高了算法性能。
本文实例讲述了Python实现的计数排序算法。分享给大家供大家参考,具体如下: 计数排序是一种非常快捷的稳定性强的排序方法,时间复杂度O(n+k),其中n为要排序的数的个数,k为要排序的数的组大值。计数排序对一定量的...
基于预排序算法、堆排序算法和计数排序算法分别编写一个排序算法。 【预排序函数原型及功能说明】 检验数组中元素的唯一性: 先对数组排序,然后只检查它的连续元素:如果该数组有相等的元素,则一定有一对元素是相互...
通常计数排序算法的实现步骤思路是: 1.找出待排序的数组中最大和最小的元素; 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项; 3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加); 4....
麻省理工学院“算法导论”课程中介绍的计数排序算法的实现。 例子 var countingSort = require ( './countingSort.js' ) ; // Construct input [0, 5], therefore an array of size 6 is needed // for the ...
该程序包含7大排序算法: ...# sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据
主要是对算法导论中计数排序的实现
数据结构与算法实验五排序,包括算法描述,代码,测试数据,具体操作等步骤,主要对应何钦铭版本的实验。下载时,请根据版本下载
2、熟练使用高级编程语言实现不同的快速排序算法。 3、利用实验测试给出不同快速排序算法的性能以理解其优缺点。 快速排序是算法导论中的经典算法。在本实验中,给定一个长为 n 的整数数 组,要求将数组升序排序。