排序
- 排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)
计数排序
- 核心思想：通过计数而非比较来进行排序，借助数组下标本身就是有序的原理实现
- 适用范围：较小的非负整数序列和最小值和最大值之间的数字范围比较合适
- 基数排序需要新增一个计数数组(待累计数组)
- 计数数组：即新的临时的初始化数组用于计数，需要找到原始数组中最大的值，再加1，才是这个数组的长度，存储 [0 ~ max]
- 累计数组：是由计数数组计算后得到的，下标是原数组的值，元素值是累计的个数，即重复的个数
算法实现
1 ）基础版本
function countSort(list) {
const len = list.length;
if (len < 2) return;
// 获取最大值
const max = Math.max.apply(null, list);
// 初始化计数数组
const countList = new Array(max + 1).fill(0); // 数组大小，存放[0~max]
// 对原数组的数据在计数数组中累计，原数组的值是计数数组的下标
let i;
for(i = 0; i < len; i++) countList[list[i]]++; // 遍历完成后计数数组就变成了累计数组
// 基于累计数组生成排好序的数组，这里利用了下标即是有序的原理
i = 0; // 重新使用i
for(let j = 0; j < max + 1; j++) {
// 内层循环不会到n, 一般是常数级别的，但是这样写似乎也不是太好，嵌套会增加时间复杂度
for (let k = 0; k < countList[j]; k++) list[i++] = j; // 这里j就是下标，其实就是原数组的值
}
}
const list = [2,3,8,7,1,2,2,2,7,3,9,8,2,1,4,2,4,6,9,2];
countSort(list);
console.log(list); // [1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]
2 ）优化版本：优化时间复杂度(空间换时间)
function countSort(list) {
const len = list.length;
if (len < 2) return;
// 获取最大值和最小值
const max = Math.max.apply(null, list);
const min = Math.min.apply(null, list);
// 初始化计数数组
const countList = new Array(max - min + 1).fill(0);
// 对原数组的数据在计数数组中累计，原数组的值是计数数组的下标
let i;
for(i = 0; i < len; i++) countList[list[i] - min]++; // 遍历完成后计数数组就变成了累计数组
// 基于累计数组生成排好序的数组，这里利用了下标即是有序的原理
let result = [];
i = 0; // 重新使用i
for(let j = 0; j < max + 1; j++) {
if (!countList[j]) continue;
countList[j] > 1 ? (result = result.concat(new Array(countList[j]).fill(j))) : result.push(j);
}
return result; // 替换
}
const list = [102,103,108,107,101,102,102,102,107,103,109,108,102,101,104,102,104,106,109,102];
const result = countSort(list);
console.log(result); // 101,101,102,102,102,102,102,102,102,103,103,104,104,106,107,107,108,108,109,109
3 ）优化版本：优化时间复杂度(空间换时间) + 优化存储空间
function countSort(list) {
const len = list.length;
if (len < 2) return;
// 获取最大值和最小值
const max = Math.max.apply(null, list);
const min = Math.min.apply(null, list);
// 初始化计数数组
const countList = new Array(max - min + 1).fill(0);
// 对原数组的数据在计数数组中累计，原数组的值是计数数组的下标
let i;
for(i = 0; i < len; i++) countList[list[i] - min]++; // 遍历完成后计数数组就变成了累计数组
// 基于累计数组生成排好序的数组，这里利用了下标即是有序的原理
i = 0; // 重新使用i
let result = [];
for(let j = 0; j < max - min + 1; j++) {
if (!countList[j]) continue;
countList[j] > 1 ? (result = result.concat(new Array(countList[j]).fill(j + min))) : result.push(j + min);
}
return result;
}
const list = [102,103,108,107,101,102,102,102,107,103,109,108,102,101,104,102,104,106,109,102];
const result = countSort(list);
console.log(result); // 101,101,102,102,102,102,102,102,102,103,103,104,104,106,107,107,108,108,109,109
