計數排序

目錄

一、基本思路

二、代碼實作

一、基本思路

    給定一個數組，先統計各個元素出現的次數，用元素的值做下标，得到一個新的數組。然後掃描這個數組，對于數組的每個下标，如果它對應值不為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;
}
           

三、運算結果