使用双路快排实现颜色排序疑问

来源:2-8 Leetcode 75: Sort Colors

坐着谷堆望着天

2024-05-27 15:45:20

老师你好,我仿照着双路排序尝试解决颜色排序的问题。

对于第一版代码

    public void sortColors(int[] nums){
        int targetValue = 1;
        int zeroBorder = 0;
        int twoBorder = nums.length - 1;

        while (true){
            while (zeroBorder <= twoBorder && nums[zeroBorder] < targetValue)
                zeroBorder++;

            while (twoBorder >= zeroBorder && nums[twoBorder] > targetValue)
                twoBorder--;

            if (zeroBorder >= twoBorder) break;

            swap(nums,zeroBorder,twoBorder);

            zeroBorder++;
            twoBorder--;
        }
    }

发现测试用例 [2,0,1] 无法通过,跟踪代码后,发现是最后的twoBorder对应的元素没有进行交换。我想是不是这种排序方式需要在所有循环结束后,进行一次赋值,于是我把代码改成了这样

public static void sortColors(int[] nums){
        int targetValue = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == targetValue){
                swap(nums,0,i);
                break;
            }
        }

        int zeroBorder = 1;
        int twoBorder = nums.length - 1;

        while (true){
            while (zeroBorder <= twoBorder && nums[zeroBorder] < targetValue)
                zeroBorder++;

            while (twoBorder >= zeroBorder && nums[twoBorder] > targetValue)
                twoBorder--;

            if (zeroBorder >= twoBorder) break;

            swap(nums,zeroBorder,twoBorder);

            zeroBorder++;
            twoBorder--;
        }

        swap(nums, 0, twoBorder);
    }

但是这种方式,测试用例[2,0,2,1,1,0] 无法通过。在跟踪代码的过程中逐渐迷惑了,想问问老师这种方式可以实现颜色排序吗

写回答

1回答

liuyubobobo

2024-05-29

使用双路快排的思路,你需要完成整个排序过程,一趟 partition 是不够的。


以用例 [2,0,2,1,1,0] 为例,一次 partition 以后,


结果为:

 [1,0,0,1,2,2]
        |
      pivot

此时你可以看到:pivot 前面的所有元素都 <= pivot 的元素,pivot 后面的所有元素都 >= pivot 的元素,这次 partition 是正确的,但是,整个排序没有完成。


==========


请再理解一下你的这个直接复用课程中双路快排的 partition 的思路,和课程这里的思路的不同:https://class.imooc.com/lesson/1582#mid=37051。课程这里的思路充分利用了这个问题的数据类型只有三种这个条件。


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2610 学习 · 1087 问题

查看课程