快速排序，sort递归误写成partition递归，竟然正确排序，速度翻倍，不解原因
来源：3-5 快速排序法 - Quick Sort
慕运维7111006
2019-02-28
bobo老师，关于快速排序基础版本代码，我无意间把sort的递归写成了partition递归，结果排序正确，还快了10倍。并且对于NearlyOrder的输入对速度也没有任何影响。这个该如何理解？
private static void sort(Comparable[] arr, int l, int r){
if(l > r)
return;
int p = partition(arr, l, r);
partition(arr, l, p-1);
partition(arr, p+1, r);
}
private static int partition(Comparable[] arr, int l, int r){
Comparable v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for(int i = l+1; i <= r; i++){
if(arr[i].compareTo(v) < 0){
j++;
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
写回答
1回答
-
这个代码显然不能正确排序。整个过程只是在sort中调用了三次partition而已。partition自己没有调用自己，也不是一个递归函数。调用三次partition不可能排序成功。（也因为这个过程只是调用了三次partition而已，所以速度很快。）
如果你的程序使用assert进行的判断，但没有中断，应该是运行时没有打开assert，可以参考这里https://coding.imooc.com/learn/questiondetail/48418.html 或者自行把代码修改成抛异常的方式。或者直接把结果打印出来看一下。
继续加油！：）
212019-02-28
相似问题