快速排序，sort递归误写成partition递归，竟然正确排序，速度翻倍，不解原因

Question

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;
}

Answer 1

liuyubobobo 2019-02-28 19:29:15

这个代码显然不能正确排序。整个过程只是在sort中调用了三次partition而已。partition自己没有调用自己，也不是一个递归函数。调用三次partition不可能排序成功。（也因为这个过程只是调用了三次partition而已，所以速度很快。）

如果你的程序使用assert进行的判断，但没有中断，应该是运行时没有打开assert，可以参考这里https://coding.imooc.com/learn/questiondetail/48418.html 或者自行把代码修改成抛异常的方式。或者直接把结果打印出来看一下。

继续加油！：）

• 提问者 慕运维7111006 #1

  确实是assert没有出来，谢谢bobo老师。