C++ 计数排序

计数排序的原理：

（1）首先，找出最大的元素，给“count[ ]”申请“最大元素的下标+1”个单元(因为数组下标是从0开始的，所以要+1)；

（2）然后，统计每个元素出现的次数，把次数存到“count[ ]”里；

（3）最后，通过一个元素出现的次数-1，从而算出正确顺序的位置，再把元素放进去，就有顺序了。

  因为不知道范围的大小，所以需要申请内存，如果知道范围的大小，就可以直接声明。

#include <iostream>
#include <stdlib.h>
using namespace std;

/**********************************************/
/*  计数排序
/*********************************************/

void CountingSort(int array[], int n)
{
	int i;
	int largest = array[0];  //设最初最大元素默认是array[0]
	int *temp = new int[n];  //申请一个n个int元素的数组内存

	for (i = 1; i < n; i++)
	{
		if (largest < array[i])  //找出最大元素
		{
			largest = array[i];
		}
	}

	int *count = new int[largest + 1];  //申请一个[largest+1]个int元素的数组内存
	for (i = 0; i <= largest; i++)
	{
		count[i] = 0;  //初始化
	}

	for (i = 0; i < n; i++)
	{
		count[array[i]]++;  //计算array数组每个元素出现的次数
	}

	for (i = 1; i <= largest; i++)
	{
		count[i] = count[i - 1] + count[i];  //count数组元素出现次数的累加
	}

	for (i = n - 1; i >= 0; i--)
	{
		temp[count[array[i]] - 1] = array[i];  //将array[]数组的元素赋给已经排好位置的temp[]数组
		count[array[i]]--;  //数组元素的总次数减少
	}

	for (i = 0; i < n; i++)
	{
		array[i] = temp[i];  //将排好顺序的元素赋给array[]数组
	}

	delete[] count;  //释放内存
	count = NULL;
	delete[] temp;  //释放内存
	temp = NULL;
}


int main(void)  //主程序
{
	const int n = 6;  //数组元素的数量
	int array[n];
	cout << "请输入6个整数：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}

	cout << endl;  //换行

	CountingSort(array, n);  // 调用CountingSort函数  进行排序

	cout << "由小到大的顺序排列后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Array" << "[" << i << "]" << " = " << array[i] << endl;
	}

	cout << endl << endl;  //换行

	system("pause");  //调试时，黑窗口不会闪退，一直保持
	return 0;
}

运行结果：