使用双路快排实现颜色排序疑问
老师你好,我仿照着双路排序尝试解决颜色排序的问题。
对于第一版代码
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] 无法通过。在跟踪代码的过程中逐渐迷惑了,想问问老师这种方式可以实现颜色排序吗
6
收起
正在回答
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 星