没有明白老师的left + index[i]的含义

没有明白老师的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

感觉自己的写的方式更好理解,但是没明白老师的写法为什么也可以?

正在回答 回答被采纳积分+1

登陆购买课程后可参与讨论,去登陆

1回答
提问者 Potter520 2023-04-08 11:09:16

明白了,其实我没有添加偏移量left,计算出来的偏移量是错误的。要加上left 才正确。想不清画了一个图就明白了

https://img1.sycdn.imooc.com//climg/6430dad2099fea3705580600.jpg

  • 大赞!继续加油!:)

    2023-04-11 06:37:04
  • 很佩服你们,各种思路都可以用图清晰的画出来,友友可以告诉一下是用什么工具画的吗?万分感谢!

    2023-11-21 16:43:23
  • 提问者 Potter520 回复 慕数据0441619 #3

    draw.io

    2023-12-03 11:25:08
问题已解决,确定采纳
还有疑问,暂不采纳

恭喜解决一个难题,获得1积分~

来为老师/同学的回答评分吧

0 星
算法与数据结构
  • 参与学习       2583    人
  • 解答问题       1082    个

慕课网算法名师Liuyubobobo,5年集大成之作 从0到工作5年,算法与数据结构系统解决方案

了解课程
请稍等 ...
意见反馈 帮助中心 APP下载
官方微信

在线咨询

领取优惠

免费试听

领取大纲

扫描二维码,添加
你的专属老师