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

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

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

对于第一版代码

    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回答

使用双路快排的思路,你需要完成整个排序过程,一趟 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。课程这里的思路充分利用了这个问题的数据类型只有三种这个条件。


继续加油!:)

问题已解决,确定采纳
还有疑问,暂不采纳

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

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

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

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

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

在线咨询

领取优惠

免费试听

领取大纲

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