java - 快速排序对除少数项目外的所有项目进行排序

Question

我花了很多时间试图找出我不正确的地方。调试等等，但我似乎无法解释为什么我的快速排序会错过一些排序项目。

我在下面复制了用于排序和分区的代码。我有一种感觉，这是一件非常明显的事情，我看得太多了，但我花了无数时间调试、研究和重写我的代码，结果总是一样。

// quicksort the subarray from a[lo] to a[hi]
private void sort(Comparable[] a, int lo, int hi) {
    if((hi-lo)>1){
        int pivot = partition(a,lo,hi);
        sort(a,lo,pivot);
        sort(a,pivot+1,hi);
    }
}

// partition the subarray a[lo .. hi] by returning an index j
// so that a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
private int partition(Comparable[] a, int lo, int hi) {
    //find middle
    int pivotIndex = (hi+lo)/2;
    //pick pivot
    Comparable pivot = a[pivotIndex];
    //create left and right pointers
    int left = lo, right = hi;
    //start comparing
    //compare until left passes right
    while(left<right){
        //while left is less than pivot move on
        while(a[left].compareTo(pivot) < 0) left++;
        //while right is greater than pivot move on
        while(a[right].compareTo(pivot) > 0) right--;
        //if the pointers have passed each other we're done
        //if a[left] is greater than a[right] swap them
        if(a[left].compareTo(a[right]) > 0){
            Comparable holder = a[left];
            a[left] = a[right];
            a[right] = holder;
            //increment/decrement
            left++; right--;
        }
    }
    return right;
}

Answer 1

只需删除left++; right--;，一切都会好起来的。