【计数排序】十大排序算法之计数排序，是稳定的排序。
目录
一、计数排序基本思想
二、计数排序实现代码
一、计数排序基本思想
- 计数排序，属于【非比较类】的排序。
- 计数排序，其实是采用了和【桶排序】一样的思想，可以说计数排序属于桶排序的一种。
- 计数排序，时间复杂度：【O(k + n)】。
- 计数排序，空间复杂度：【O(n)】。
什么是稳定的排序？？？
稳定排序：
- 如果排序数组中，存在相同的元素，假设存在两个元素【3】。
- 为了标识两个元素【3】的先后顺序，我们假设给她命名为：【3(1)】、【3(2)】。
- 其中括号里面的表示元素3出现的先后顺序。
- 如果结果排序之后，两个元素还是保持相同的顺序，即：【3(1)、3(2)】，那么我们就称这个排序是稳定的，否则就是不稳定的排序。
计数排序基本思想
计数排序，最关键的是利用【空间换取时间】的方式，利用额外空间保存待排序数组中每个元素的实际出现位置，然后遍历额外空间数组，输出每个元素，得到的就是有序序列了。
基本思想：
- 遍历待排序数组【arr】，找到数组中最大值【max】和最小值【min】。
- 创建一个大小为【max - min + 1】的数组【count】，这个数组就是用于保存待排序数组中每个元素的出现次数。
- 遍历数组【arr】，找到每个数组元素在【count】数组中的正确位置，然后【count】数组位置加【1】。
- 循环结束，遍历【count】数组，输出数组中每个位置元素。
- 遍历结束，输出结果就是有序的数组。
计数排序大致思想如下图所示：
可以从这个网站查看计数排序的过程【数据结构和算法动态可视化 (Chinese) - VisuAlgo】。
二、计数排序实现代码
计数排序实现代码：
public class CountSort {
public static int[] countSort(int[] nums) {
// 结果数组
int[] ans = new int[nums.length];
// 找出待排序数组最大值和最小值
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 创建计数数组
int[] count = new int[max - min + 1];
// 将待排序数组元素放到计数数组正确位置
for (int i = 0; i < nums.length; i++) {
count[nums[i] - min]++;
}
// 确定计数数组中每个元素的排序位置
for (int i = 1; i < count.length; i++) {
// 这里表示: 当前元素应该在 ans 数组中第几个位置
// 这里其实有点难理解,需要画个图理解一下,请看下面的图
count[i] += count[i - 1];
}
// 将元素有序的复制到结果数组, 从后往前遍历能够保证排序的稳定性
for (int i = nums.length - 1; i >= 0; i--) {
// 将当前待排序的元素放到 ans 结果数组正确位置
// nums[i] - min -> 表示当前元素对应计数数组哪个下标
// count[nums[i] - min] -> 表示当前元素应该放到 ans 数组哪个下标位置
// --count[nums[i] - min] -> 减1表示当存在重复元素时候, 对应 ans 下标就往前移动一位了
ans[--count[nums[i] - min]] = nums[i];
}
// 返回排序数组
return ans;
}
public static void main(String[] args) {
int[] nums = { 4, 1, 7, 3, 12, 6, 9, 4 };
System.out.println(Arrays.toString(nums));
int[] ans = countSort(nums);
System.out.println(Arrays.toString(ans));
}
}
排序结果如下所示：
部分代码画图分析理解一下
// 确定计数数组中每个元素的排序位置
for (int i = 1; i < count.length; i++) {
// 这里表示: 当前元素应该在 ans 数组中第几个位置
// 这里其实有点难理解,需要画个图理解一下,请看下面的图
count[i] += count[i - 1];
}
上面这一段代码什么意思呢？？？它其实就是确定当前元素应该在排序后的第几个位置，看下面的图解。
我们还是以【4, 1, 7, 3, 12, 6, 9, 4】数组为案例，它的计数数组结果是：【1, 0, 1, 2, 0, 1, 1, 0, 1, 0, 0, 1】。
这样将【count】数组中的元素变成对应【ans】结果数组中的下标，这就后面取出数据元素就方便很多。
// 将元素有序的复制到结果数组, 从后往前遍历能够保证排序的稳定性
for (int i = nums.length - 1; i >= 0; i--) {
ans[--count[nums[i] - min]] = nums[i];
}
这一段代码的含义就是从【count】数组中取出元素，然后放到【ans】结果数组正确的位置。
注意：这里是从【nums】中倒序取出元素的，为什么是倒序呢？？？因为倒序取出可以保证计数排序的稳定性。
下面看下图解就知道为什么正序不能保证稳定性了。
综上，就是计数排序相关思想，以及代码实现。
