本文主要介绍Counting Sort（计数排序）算法的相关知识，同时通过示例代码介绍这种算法的常见用法。
1 概述
Counting sort是一种基于给定范围数值的排序技术。该算法首先计算给定输入序列（如数组）中每个对象的数量，同时将对象数量值存储在临时数组的对应索引处，最后通过一系列算术操作计算出每个对象在输出序列中的位置。
2 特点
Counting sort算法的特点如下：
- counting sort会对输入序列进行假设。例如，假设输入序列中的数值范围为0到10，或10到99，等等。某些场景下，counting sort也会假设输入数据为所有实数；
- counting sort不是一个基于比较的排序算法，它将输入数据散列（hash）到一个临时计数数组中，然后再进行排序；
- 由于counting sort需要使用临时数组，因此它不是一个原地算法（In-place algorithm）。
一般来说，输入序列取值范围在1到10K之间，都可以考虑使用counting sort算法。
3 常见用法
虽然counting sort是一种排序算法，但是我们可以利用该算法的核心思想来解决一些其他问题。
3.1 存储输入数据中每个元素的出现次数
假设有一组取值范围为0到9的数字，现要求存储每个数字的出现次数。
对于这个问题，就可以使用counting sort思想了。
例如，假设输入序列为：{1, 4, 1, 2, 7, 5, 2}，则此问题的解答步骤如下：
1. 新建一个长度为10（因为输入数据的取值范围为0到9）的临时数组，如下图：
2. 统计输入序列的中每个元素的出现次数。元素每出现一次，就根据该元素的值匹配临时数组中对应的索引，然后将该索引对应的数组值（次数值）加1，如下图：
3. 遍历过输入数据后，就可以得到的存储输入数据元素出现次数的临时数组了，如下图：
至此，本问题解答完成。
3.2 Count Number of Pairs With Absolute Difference K
下面通过LeetCode中的一道题，来介绍couting sort的应用。
3.2.1 题目描述
2006. Count Number of Pairs With Absolute Difference K
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.
The value of |x| is defined as:
x if x >= 0.
-x if x < 0.Example 1:
Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: The pairs with an absolute difference of 1 are:
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]Example 2:
Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.Example 3:
Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
- 1 <= k <= 99
3.2.2 解题思路
由于输入数据是一个整型数组，同时存在“1 <= nums[i] <= 100”这条约束，因此可以考虑使用counting sort方法来解决。
先使用counting sort方法来生成一个存储输入数据中每个元素出现次数的临时数组，再根据题目要求，找出临时数组中间距为k的数字对数，该数字对数即为此题答案。
解决方案代码如下：
class Solution {
public:
int countKDifference(vector<int>& nums, int k) {
int count = 0;
vector<int> v(101);
for (auto i:nums) {
++v[i];
}
// as 1 <= nums[i]
for (int i = 1; i + k < v.size(); i++) {
count += v[i] * v[i + k];
}
return count;
}
};