计数排序

算法思想

计数排序是一种基于非比较的一种排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，计数排序要求输入的数据必须有明确的范围。

算法步骤：

1. 查找数组中的最大数和最小数
2. 根据最大数和最小数生额外的辅助数组（max-min+1）
3. 在辅助数组对应位置记录原数组每个数字出现的次数
4. 根据辅助数组调整原始数组

举个简单的例子 arr = [2,0,-2,-1,3,1,3]，最小数字min=-2，最大数字max=3，所以产生一个长度为（3-（-2）+1）= 6的辅助数组countArr

下一步就是从头遍历arr数组，数字2对应的在countArr中的位置是 2-min = 4，数字-1在countArr中对应的位置为-1-min = 1。通过这样计算 可以得到每个数字在countArr中对应的位置，并计数，就会得到下面的结果

然后把对应的数字每个统计的数字从小到大的更新到原始数组中就完成了排序。

对于计数排序来说，它是一种稳定的排序算法，只需要把数组遍历一次就可以完成排序，所以时间复杂度为 $O(n)$O(n)，但是在反向填充原始数组的过程中，需要遍历的辅助数组的长度为 $n+m$n+m ，所以整体排序的时间复杂度为 $O(n+m)$O(n+m)，空间复杂度为 $O(n+m)$O(n+m)。

看样下面的动画演示

代码实现

#include <iostream>
#include <vector>

using namespace std;

/*
* 计数排序
*/
void countSort(vector<int>& vec) {
    // 数量少于两个直接返回
	if (vec.size() < 2) {
		return;
	}
    
	int min = vec[0];  // 定义最小值并初始化
	int max = vec[0];  // 定义最大值并初始化
    // 查找数组中的最小值和最大值
	for (int i = 0; i < vec.size(); i++) {
		min = min < vec[i] ? min : vec[i];   
		max = max > vec[i] ? max : vec[i];
	}
	// 如果最大值和最小值相等，表示数组中的数字都是相同的，直接返回
	if (min == max) {
		return;
	}

	vector<int> countVec(max - min + 1, 0);  // 开辟一个max-min+1长度大小的数组，并初始化

    // 遍历数组中的每个元素并计数
	for (int i = 0; i < vec.size(); i++) {
		countVec[vec[i] - min]++;
	}
    
	int index = 0;  // 用于记录原始数组的下标
    // 把辅助数组更新到原数组中
	for (int i = 0; i < countVec.size(); i++) {
        // 直到计数减为零，在进行下一次循环
		while (countVec[i]) {
			vec[index] = i+min; 
			index++;
			countVec[i]--;
		}
	}
}

int main() {
	vector<int> arr = { -1, 2, 0, 4, 3, 6, 5, 8, -2, 1, 3, 0, 3, 6, 5, 2 };
	countSort(arr);
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;

	return 0;
}

总结

• 稳定性：稳定
• 时间复杂度：$O(n+m)$O(n+m)
• 空间复杂度：$O(n + m)$O(n+m)

欢迎大家关注我的个人公众号，同样的也是和该博客账号一样，专注分享技术问题，我们一起学习进步