关于双路快排的partition实现
来源：2-3 实现双路快速排序法
sadcloud
2021-04-01 12:57:26
bobo老师，我刚学习快排，并不认为您partition函数实现的代码风格好，您看我的质疑有道理吗？
您的实现：
private static int partition(int[] arr, int l, int r) {
int i = l+1;
int j = r;
while(true){
while(i<=j && arr[i]<arr[l]) //replace the i<=j with i<arr.length is also ok~
i++;
while(i<=j && arr[j]>arr[l]) //the condition i<=j is always ture.
j--;
if(i>=j){
break;
swap(arr,i,j);
}
i++;
j--;
}
swap(arr,l,j);
return j;
}
老师您看我加入的两个注释（因为我自己实现的时候漏掉了i<=j的条件，想当然的认为只要a[i]<a[l]成立时，i<=j当然是满足的。没有注意到如果arr[l]是最大的元素时，r=arr.length-1的partition过程中的第一个while循环中的最后一次判断arr[i]会越界
） 所以按照我注释的内容修改后逻辑也是正确的（而您两个while循环中第一个条件都直接i<=j，我认为有些"冗余"了）。
第二个问题就是我第一次看您写的while(true)感觉很奇怪(因为以前从来没写过)，后来发现其实这是do while循环呀，可能如下实现更容易理解些？（提问修改：好吧，我现在也并不觉得哪种更好了，只觉得写法真的多变，感觉只能第一感觉是什么思路就按照什么思路实现了）
循环不变量由您定义的：
arr[l+1,i)<=arr[l]
arr(j,r]>=arr[l]
也增强成：
arr[l+1,i)<=arr[l] && arr[i]>=arr[l]
arr(j,r]>=arr[l] && arr[j]<=arr[l]
相关代码：
private static int partition(int[] arr, int l, int r){
//arr[l+1,i)<=arr[l], arr(j,r]>=arr[l] → i=j;
int i = l+1;
int j = r;
while(i<arr.length && arr[i]<arr[l])
i++;
while(arr[j]>arr[l])
j--;
while(i<j){
// loop invariant: arr[l+1,i)<=arr[l] && arr[i]>=arr[l]
// arr(j,r]>=arr[l] && arr[j]<=arr[l]
swap(arr,i,j);
do{
i++;
}while(arr[i]<arr[l]);
do{
j--;
}while(arr[j]>arr[l]);
}
swap(arr,j,l);
return j;
}
一点小小思考，请老师指点
1回答
-
赞实验精神。我测试了一遍你的代码，没有问题。
我来简单解释一下我的代码风格。
首先，代码风格是没有绝对的正确和错误的，自己习惯就好。
1
对于你在 1 提出的问题。是的，第一个 while 中写成 i < arr.length 没问题；第二个 while 中不写 i <= j 没有问题。但是，我认为我的写法，是“思维负担”最小的写法。在 ppt 模拟中，我们的 i 就在 j 的左边，所以，我直接写成 i <= j，我也不在乎是否 i 根本不会大于 j，反正我要的是 i <= j。
这有点儿像这个问题：https://class.imooc.com/course/qadetail/249635
你可以说在你的场景下，getCapacity() / 2 != 0 这个条件没有用，冗余。但我认为，因为下面有 resize(getCapacity() / 2)，那我就对 getCapacity() / 2 是否为 0 做一下判断。而不需要考虑这个条件是否是永远不能满足的。这在我看来是思维负担最小的方式。
或者我遇到 a / b 这样的算式，就判断一下 b != 0，哪怕在我们的逻辑中，b 永远不会为 0，我也判断一下，他不会错，且我不会绞尽脑汁去想，b 是不是真的永远不会为 0，不写这样一个条件会不会产生 bug。
2
相信你在写这个逻辑的时候已经意识到了，这不是一个简单的 do while，所以在你的逻辑里，先有了两重 while，然后再有一重 while，这个 while 里有两个 while。
而我的逻辑把你外面三层 while 统一了。
while(true) 确实可能是一个不够好的编程实践，但依然是，我认为在这个例子里，他的“思维负担”是最轻的。这个 while 完全是我的 ppt 动画的模拟。我们需要“重复”地先右移 i，再左移 j。只不过在写这个逻辑过程中，我发现这个“重复”的结束条件，似乎不能在 while 中判断。那么好吧，先写成 while(true)。在逻辑里，发现退出的时机也不完全在最后，那么好吧，就不改成 do while 了，中间 break。
是否可能有不要 while(true) 和 break 的控制流方式？肯定有。但在这里，我不想花时间了。因为修改这个控制流，在我看来，是形式大于内容的。
这个 while(true) 的逻辑，我认为很清晰。里面做的事情：1. 右移 i；2, 左移 j；3, 如果 i>=j 退出；4 不然，交换，i++, j--，继续循环。
我可以把这个逻辑在表达的简练一些，里面就 4 行，来描述这四件事儿：
while(true){ while(i <= j && arr[i].compareTo(arr[l]) < 0) i ++; while(i <= j && arr[j].compareTo(arr[l]) > 0) j --; if(i >= j) break; swap(arr, i ++, j --); }我们不聊编程规范，这个代码，就是我的 while(true) 的框架。这个框架涵盖了整个循环过程，没有其他边界需要考虑。我认为很清晰。
顺便一提，我相信我们都知道 goto 是一个不好的编程实现。但其实 C/C++ 仍然保留着 goto 关键字。在一些情况，我认为使用 goto 是没有问题的。滥用当然不行，但是为了没有 goto 而没有 goto，宁可扔掉 goto 也要增加代码的理解难度，我认为也不可取。
当然，这是我的编程哲学和代码风格。依然是，我不认为我一定正确的。这件事儿没有绝对的对与错，只能探讨交流：）
再赞你的思考！：）
继续加油！：）
P.S. 在这个课程中的代码，我确实不敢肯定所有的地方，我的代码都是那么合理的：）
3
相似问题