计数排序

目录

一、基本思路

二、代码实现

一、基本思路

    给定一个数组，先统计各个元素出现的次数，用元素的值做下标，得到一个新的数组。然后扫描这个数组，对于数组的每个下标，如果它对应值不为0，说明元来数组中就有几个这样的值。由于下标的天然递增，依次将这些值展开就得到排序后的数组。

    但是计数排序有它的局限性，首先如果想用数组统计各个元素出现的次数，它的值必须是正整数。如果你想用map来统计次数的话，那么它无法保证下标的递增特性。（某些语言的map实现可能会自动按照下标排序，但复杂度就是另一回事了）。

1、花O(n)的时间扫描一下整个序列A,获取最小值min和最大值max。

2、开辟一块新的空间创建新的数组B，长度为(max - min + 1)。

3、数组B中index的元素记录的值是A中某元素出现的次数。

4、最后输出目标整数序列，具体逻辑是遍历数组B，输出相应元素及对应个数。

二、代码实现

/*======================================================
*
*程序说明：	C++计数排序实现
*运行平台：	Linux/Windows
*创建日期：	20190517
*作	  者：	LiuHuan
*
*======================================================*/

#include <iostream>
#include <vector>
#include <time.h>	// 随机数种子
#include <chrono>	// 统计运行时间需要

using namespace std;
using namespace chrono;

#define RUN_SORT(FUNC)	\
{	\
	auto tStart = system_clock::now();	\
	FUNC;	\
	auto tEnd = system_clock::now();	\
	auto tCost = duration_cast<nanoseconds>(tEnd - tStart);	\
	cout << "耗时: " << tCost.count() << " ns(纳秒).\n" << endl;	\
}

// 随机返回正负
int Symbol(int num)
{
	return (num == 1 ? 1 : -1);
}

// ************************************ 计数排序核心代码部分
// 目前仅支持非负数列
void CountSort(vector<int>& vec)
{
	// 先找到最大值
	int max = vec[0];
	for (auto it : vec)
	{
		max = max > it ? max : it;
	}

	// 扫描一遍，记录各元素出现次数,下标为值，存储内容为出现次数
	vector<int> vecCount;
	vecCount.resize(max + 1);	// 注意为何此处只需max + 1即可？
	for (auto it : vec)
	{
		vecCount[it]++;
	}

	// 对出现每个元素，按照出现次数，依次展开到目标数组
	vec.clear();
	for (size_t i = 0; i < vecCount.size(); i++)
	{
		int occurTimes = vecCount[i];
		while (occurTimes--)
		{
			vec.push_back(i);
		}
	}
}
// ************************************

template<typename T>
void printVec(const vector<T>& vec)
{
	int cnt = 1;
	for (auto it : vec)
	{
		cout << it << "\t";
		if (cnt++ % 10 == 0)	// 每十个换行输出
		{
			cout << "\n";
		}
	}
	cout << "\n\n";
}

int main()
{
	srand((unsigned int)time(NULL));
	int cnt = 1;
	do
	{
		vector<int> vec;
		for (size_t i = 0; i < 10; i++)		// 注意这里元素值和序列大小的选取对排序性能有影响，建议读者自己改变参数调试, 研究一番
		{
			// int value = Symbol(rand() % 2) * rand() % 1000;
			int value = rand() % 1000;	// 目前仅支持非负数列
			vec.push_back(value);
		}
		cout << "************第[ " << cnt << " ]次计数排序前序列：\n";
		printVec(vec);

		RUN_SORT(CountSort(vec))

		cout << "排序后序列：\n";
		printVec(vec);

	} while (cnt++ < 5);

	//system("pause");  // linux关闭，VS打开
	return 0;
}
           

三、运算结果