没有明白老师的left + index[i]的含义
/**
* Most Significant Digit: 最重要的位,从左往右
* @param {*} arr
*/
function msdSort(arr) {
function sort(arr, left, right, r) {
if (left >= right) {
return;
}
let R = 3;
let cnt = Array(R + 1).fill(0);
let index = Array(R + 2).fill(0);
let temp = Array(right - left + 1).fill("");
let ACode = "A".charCodeAt(0);
for (let i = left; i <= right; i++) {
let code = r >= arr[i].length ? 0 : arr[i][r].charCodeAt(0) - ACode + 1;
cnt[code]++;
}
for (let i = 0; i + 1 < index.length; i++) {
index[i + 1] = index[i] + cnt[i];
}
for (let i = left; i <= right; i++) {
let code = r >= arr[i].length ? 0 : arr[i][r].charCodeAt(0) - ACode + 1;
temp[index[code]] = arr[i];
index[code]++;
}
for (let i = left; i <= right; i++) {
arr[i] = temp[i - left];
}
//! 方式1:重置区间索引
/* index.fill(0);
for (let i = 0; i + 1 < index.length; i++) {
index[i + 1] = index[i] + cnt[i];
}
for (let i = 0; i + 1 < index.length; i++) {
let tl = index[i];
let tr = index[i+1] - 1;
sort(arr, tl, tr, r + 1);
}
*/
//! 方式2:不重置,偏移一个区间,所以用i-1
/* for (let i = 1; i < index.length; i++) {
let tl = index[i - 1];
let tr = index[i] - 1;
sort(arr, tl, tr, r + 1);
} */
//! 方式2:不重置,偏移一个区间,由于排序后index[i]已变成原来的index[i+1]值,所以最后一个区间index[i]和index[i+1]重合,所以最后一个区间无需再遍历
/* for (let i = 1; i < index.length - 1; i++) {
let tl = index[i - 1];
let tr = index[i] - 1;
sort(arr, tl, tr, r + 1);
} */
//! 没太明白为啥是left+index[i]
for (let i = 0; i < R; i++) {
let tl = left + index[i];
let tr = left + index[i + 1] - 1;
sort(arr, tl, tr, r + 1);
}
}
sort(arr, 0, arr.length - 1, 0);
return arr;
}
let arr = ["ABC", "ACB", "AB", "BC", "BAC", "CAB", "CBA"];
msdSort(arr);
for (const str of arr) {
console.log(str);
}
输出结果
AB
ABC
ACB
BAC
BC
CAB
CBA
感觉自己的写的方式更好理解,但是没明白老师的写法为什么也可以?
16
收起
恭喜解决一个难题,获得1积分~
来为老师/同学的回答评分吧
0 星