计数排序
计数排序非常容易理解，相信等我介绍完概念，大家都可以写出来。
通过数组下标来记录数列中各数的值，通过下标对应的值来记录相同数出现的频率。打个比方，一个长度为10的数组，下标为0-9，如果我们要排序的数列为0-9之间的随机数，如list = [0, 0, 8, 3, 4, 2, 7, 7, 7, 5]，要将其从小到大排列：
- 声明一个下标计数数组为
sortArray = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]，初始值都为0； - 遍历list，每个元素大小对应下标的值在计数数组中加1，如遍历完前三个数后，sortArray变成了
[2, 0, 0, 0, 0, 0, 0, 0, 1, 0]。 - 结束后再遍历sortArray打印出有序的数列。
是不是很简单呢，代码如下：
需要注意，一开始我们是不确定数列的最大值的，所以我们要先找到数列中的最大值max，并将sortArray的长度设为max + 1，保证最大值可以找到其对应的下标
function countSort(list: number[]): number[] {
let max = 0;
for (let i = 0; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
}
const sortArray: number[] = new Array(max+1);
list.forEach(item => {
if (sortArray[item] === undefined) {
sortArray[item] = 0;
}
sortArray[item]++;
});
const res = [];
sortArray.forEach((sort, index) => {
if (sort > 0) {
for (let i = 0; i < sort; i++) {
res.push(index);
}
}
});
return res;
}
这样是可以实现了排序，但是还可以进行优化，如果我们要排列的数组为[99, 98, 97, 93, 95]呢？最大值为99，所以我们建了一个长度为100的数组，而实际只利用了下标为93-99这一段空间。所以我们可以建立一个长度为max - min + 1的数组，来进行计数。最后统计的时候每个元素都加上最小值min即可。
function countSort(list: number[]): number[] {
let max = 0;
let min = 0;
for (let i = 0; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
if (list[i] < min) {
min = list[i];
}
}
const sortArray: number[] = new Array(max - min + 1);
list.forEach(item => {
const index = item - min;
if (sortArray[index] === undefined) {
sortArray[index] = 0;
}
sortArray[index]++;
});
const res = [];
sortArray.forEach((sort, index) => {
if (sort > 0) {
for (let i = 0; i < sort; i++) {
res.push(index + min);
}
}
});
return res;
}
上述方法只是记录了某个数出现的频率，并没有真正将输入的数列排列成有序的，造成了我们容易分不清相同大小的值谁在前谁在后。
改进：
-
将统计数组sortArray进行处理，让其变成值为代表输入数列为该下标的元素的排名；
如[5, 5, 9, 0, 4]进行统计并处理的过程如下：从第二个元素开始，每个元素的值为前面所有值的和，因为我们是从小到大排序，所以在sortArray前面出现的元素，在输出结果中排名肯定是比后面的高
image.png 从后往前（为了保证排序稳定性）遍历输入数组，利用其值value找到sortArray中对应下标的元素item（处理完该元素后，该item的值应该减一，因为下次再出现相同的值，由于排序稳定性，应该是排名靠前一位的），item就代表着value元素在最终的输出结果中的位置排名。
function countSort(list: number[]): number[] {
let max = 0;
let min = 0;
for (let i = 0; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
if (list[i] < min) {
min = list[i];
}
}
const sortArray: number[] = new Array(max - min + 1);
list.forEach(item => {
const index = item - min;
if (sortArray[index] === undefined) {
sortArray[index] = 0;
}
sortArray[index]++;
});
for (let i = 1; i < sortArray.length; i++) {
// 排名递增
if (sortArray[i] === undefined) {
sortArray[i] = 0;
}
sortArray[i] += sortArray[i - 1];
}
const res = new Array(list.length);
list.forEach(value => {
const realIndex = value - min;
res[sortArray[realIndex] - 1] = value;
sortArray[realIndex]--;
});
return res;
}
总结
- 计数排序只适合在一定范围内的整数排序；
- 极值差为m，输入规模为n，其时间复杂度为O(n+m)（遍历了三次输入数组，3n省略了系数），空间复杂度为O(m)（sortArray长度为m）
桶排序
基本思想就是：
- 创建桶，方法有很多，一般来说对n个数进行排序就创建n个桶，可以把桶当作一个链表，一堆桶当作一个数组；
- 确定每个桶的存值区间，方法也很多，一般来说是输入数列的极值差（max-min）除以个数n为一个区间值，每个桶之间间隔一个区间值；
- 遍历输入数列
list，将其按照区间存放到桶内，同一个桶内可能存在0个或多个值； - 遍历桶，将其内部值进行排序；
- 遍历桶，输出所有元素，得到有序数列。
function sortByBucket(list: number[]) {
let max = list[0];
let min = list[0];
for (let i = 1; i < list.length; i++) {
if (list[i] > max) {
max = list[i];
}
if (list[i] < min) {
min = list[i];
}
}
const dValue = max - min;
// 确定桶的存值区间
const partValue = dValue / (list.length - 1);
// 建桶
const bucket: number[][] = [];
for (let i = 0; i < list.length; i++) {
bucket.push([]);
}
// 插值
for (let i = 0; i < list.length; i++) {
const index = Math.floor((list[i] - min) / partValue);
bucket[index].push(list[i]);
// 内部排序
for (let i = bucket.length - 1; i > 1; i--) {
const singleBucket = bucket[index];
if (singleBucket[i - 1] > singleBucket[i]) {
singleBucket[i - 1] = singleBucket[i] ^ singleBucket[i - 1];
singleBucket[i] = singleBucket[i] ^ singleBucket[i - 1];
singleBucket[i - 1] = singleBucket[i] ^ singleBucket[i - 1];
}
}
console.log(bucket)
}
// 输出
const res = [];
for (let i = 0; i < bucket.length; i++) {
res.push(...bucket[i]);
}
return res;
}
总结
image.png
