三路快排疑问
来源：3-5 三路快排partition思路的应用 Sort Color
慕粉3884565
2021-07-29
var sortColors = function(nums) {
let l = -1;
let r = nums.length;
for(let i=0;i<r;){
if(nums[i] === 1){
i++;
}else if(nums[i] === 2){
r--;
[nums[i],nums[r]] = [nums[r],nums[i]];
}else if(nums[i] === 0){
l++
[nums[l],nums[i]] = [nums[i],nums[l]];
i++
}
}
console.log(nums);
};老师我不懂的是为什么，初始两个坐标都必须是不在有效期，一般情况下都是初始值是0，末尾是leng-1，我运行你的方法是正确，这个我做草稿也想不清楚，另外还有个问题，快排和这个差别是，我不知道怎么回事感觉脑子转的慢，很多排序方法看的头大
1回答
-
这个课程没有具体讲解三路快排，如果对这里有疑问，我强烈建议你看我的这个课程：会非常系统的讲解在书写算法的过程中，这些变量的初值到底是怎么来的：https://class.imooc.com/sale/datastructure
实际上，我们学习快排等算法的意义也在这里。我们实际在工作中不需要手写排序，但通过学习这些经典算法，我们学到的是这些算法背后的思想，已经逻辑书写的思想。
==========
具体回答这个问题，就是因为，整个程序的循环不变量是，[0, l] 区间的元素是 1，[r, n - 1] 区间的元素是 3（中间就是 2）。
在初始的时候，这两个区间都是空区间，也就是初始，我们没有处理任何元素，所以任何元素都不在任何区间里，随着程序的运行，我们把元素一点一点加到对应的区间里。所以初始的时候，左边区间是 [0, -1]，即空区间；右边区间是 [n, n - 1]，也是一个空区间。
当然，我们可以对区间的定义改变，这样我们的初值和逻辑也可以跟着变，写出正确的代码。在这个课程中，我以二分搜索为例，展示了这一点，可以参考这两小节的内容：
https://coding.imooc.com/lesson/82.html#mid=2656
https://coding.imooc.com/lesson/82.html#mid=2657
不要记什么“一般情况”，写程序，尤其是写算法，关键是组建逻辑，所有的变量，初值，都是为逻辑服务的。
继续加油！：）
032021-07-31
相似问题