计数排序——蓝桥杯培训
B站视频演示地址：https://www.bilibili.com/video/BV1GW411H7Cs/
概念：计数排序是一个非基于比较的排序算法，而是利用数组下标来确定元素的正确位置。用辅助数组对数组中出现的数字技术，元素转下标，下标转元素。
假设元素均大于等于0，一次扫描原数组，将元素值K记录在辅助数组的K位上。
1，基础版计数排序
假定20个随机整数的值如下：
9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9
创建一个辅助数组（长度为最大值+1）
先遍历这个无序的随机数列，每一个整数按照其值对号入座，对应数组下标的元素进行加1操作。
比如第一个整数是9，那么数组下标为9的元素加1：
image.png
第二个整数是3，那么数组下标为3的元素加1：
image.png
继续遍历数列并修改数组。。。。。。
最终，数列遍历完毕时，数组的状态如下：
image.png
遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10
public static void countSort1(int[] arr) {
int max = arr[0];
for (int i : arr) {
if (i > max) {
max = i;
}
}
int[] countarr = new int[max + 1];
for (int j : countarr) {
countarr[j]++;
}
int current = 0;
for (int i = 0; i < countarr.length; i++) {
while (countarr[i] > 0) {
arr[current] = i;
countarr[i]--;
current++;
}
}
}2，改进版：
public static void countSort(int[] arr) {
// 找到arr的最大值和最小值
int min = arr[0];
int max = arr[0];
for (int i : arr) {
if (i < min) {
min = i;
}
if (i > max) {
max = i;
}
}
// 创建计数数组
int[] countArr = new int[max - min + 1];
for (int j : countArr) {
countArr[j - min]++;
}
// 定义指针
int current = 0;
// 回填
for (int i = 0; i < countArr.length; i++) {
while (countArr[i] > 0) {
arr[current] = i + min;
current++;
}
}
}3，最终版
public static int[] countArr3(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i : arr) {
if (i < min) {
min = i;
}
if (i > max) {
max = i;
}
}
// 创建计数数组
int[] countArr = new int[max - min + 1];
for (int j : countArr) {
countArr[j - min]++;
}
// 对计数数组的元素进行累加，累加的规则将前一个元素的值+当前元素的值
for (int i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i - 1];
}
// 创建一个数组，存储最终的有序数列
int[] sortedArr = new int[arr.length];
// 回填
for (int i = arr.length - 1; i >= 0; i--) {
sortedArr[countArr[arr[i] - min] - 1] = arr[i];
countArr[arr[i] - min]--;
}
return sortedArr;
}以上皆为笔记
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读