今天上午老韩专门去翻了下最新的NOI大纲。电子版的大纲发布页地址:

https://www.noi.cn/xw/2023-03-15/788060.shtml

老韩做信奥这块也是一个学习的过程，目前我们只专注于入门级，入门级对排序的要求是 冒泡排序、选择排序、插入排序和今天要讲的计数排序。

前面我们已经分别对冒泡排序、选择排序、插入排序进行了讲解。

信奥算法之一文搞懂冒泡排序

信奥算法之一文搞懂选择排序

信奥算法之一文搞懂插入排序

接下来进入到今天的内容，一起看下计数排序。

通过上面的图，计数排序应该是目前接触到的排序算法中最容易理解的。算法步骤如下：

1. 找到待排序序列arr的最大值m；
2. 构建一个新的数组tmp，数组tmp长度为m+1；
3. 遍历待排序数组arr，将值为i的数据放到新数组tmp的下标为i的位置，如果有多个相同的值，进行累加操作；
4. 反向填充数组。将tmp的下标i依次放入arr的第i项arr[i]，每放入依次，tmp[i]需要减1.

理解的重点在于：临时数组的下标是待排序数组的值，临时数组某个下标的值，是这个下标在待排序数组中出现的次数。

代码在下面（代码做了详细的注释，不理解的话多读几遍，难理解的是回写的时候）：

#include <iostream>
#include <cstring>
using namespace std;

int getMaxNumber(int arr[], int length){
	int maxNumber = arr[0];
	for(int i=1;i<=length;i++){
		if(maxNumber < arr[i]){
			maxNumber = arr[i];
		}
	}
	return maxNumber;
}

/**
 * 定义一个计数排序的函数，传入数组的数组的长度
 **/
void countingSort(int arr[], int n)
{
	int maxNumber = getMaxNumber(arr, n); // 获取待排序数组的最大值
	int tmpLength = maxNumber+1; // 临时数组的长度
	int tmp[tmpLength] = {0}; // 定义临时数组，长度为待排序数组的长度+1，所有的值都为0
	
	// 下面的循环将待排序数组的值作为了临时数组的下标，如果值重复，临时数组的这个位置的值会不断+1
	for(int i=0;i<n;i++){
		tmp[arr[i]]++;
	}
	// 下面的部分是将临时数组的数据写回到原数组
	int sortedIndex = 0; // 写回数组的时候要从0开始
	for(int i=0;i<tmpLength;i++){
		while(tmp[i] > 0){ // 如果临时数组的值大于0，则说明临时数组的下标还没完全回写到原数组中
			arr[sortedIndex++] = i; //回写的时候，写的是临时数组的下标，不是临时数组的值
			tmp[i]--; // 临时数组某个下标的值是原数组这个值出现的次数 tmp[1]=3 说明原数组有三个1
		}
	}
}
int main()
{
	int arr[] = {64, 34, 25, 12, 22, 11, 90};  // 要排序的一维数组
	int n = sizeof(arr) / sizeof(arr[0]);  // 获取数组的长度，sizeof用来获取当前对象在内存中占用的大小
	cout << "排序前的数组为: ";
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	countingSort(arr, n);   // 调用排序函数
	cout << "\n 排序后的数组为: ";
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}