三路快排疑问

Question

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，我运行你的方法是正确，这个我做草稿也想不清楚，另外还有个问题，快排和这个差别是，我不知道怎么回事感觉脑子转的慢，很多排序方法看的头大

Answer 1

liuyubobobo 2021-07-30 03:14:15

这个课程没有具体讲解三路快排，如果对这里有疑问，我强烈建议你看我的这个课程：会非常系统的讲解在书写算法的过程中，这些变量的初值到底是怎么来的：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

不要记什么“一般情况”，写程序，尤其是写算法，关键是组建逻辑，所有的变量，初值，都是为逻辑服务的。

继续加油！：）

• 提问者 慕粉3884565 #1

  谢谢老师，后来我拿你的程序debug了，把我的程序debug后来终于找到解决方案答案不理想，截图我放在上面，现在我找到了学习算法方法，算法看不懂先debug

• liuyubobobo 回复 提问者 慕粉3884565 #2

  赞！debug 非常非常重要。继续加油！：）

• 提问者 慕粉3884565 #3

  非常感谢！