更改我的quickSort算法Java中的数据透视

Question

我使用数组中的第一个元素作为枢轴实现了一个有效的quickSort算法，如下所示：

public int[] quickSort( int[] a, int start, int end){

    int l = start;
    int r = end;

    int pivotIndex = start; //<---- first element in the array as pivot!

    // must be at least two elements
    if ( end - start >= 1){

        // set pivot
        int pivot = a[pivotIndex];


        while ( r > l ){
            // scan from the left
            while ( a[l] <= pivot && l <= end && r > l  ){
                l++;
            }
            while ( a[r] > pivot && r >= start && r >= l){
                r--;
            }
            if ( r > l ){
                this.swap(a, l, r);
            }
        }
        this.swap(a, pivotIndex, r);

        System.out.println("calling quickSort on " + start + " and " + (r-1));                 
        quickSort(a, pivotIndex, r - 1); // quicksort the left partition
        System.out.println("calling quickSort on " + (r+1) + " and " + end);
        quickSort(a, r + 1, end);   // quicksort the right partition

    } else {
        return a;
    }

    return a;
}

效果很好，但是如果我将更pivotIndex改为可以int pivotIndex = end;得到以下结果：

run:
2, 8, 7, 1, 3, 5, 6, 4, 
2, 8, 7, 1, 3, 5, 6, 4, 
swapping l:8 and r:4
2, 4, 7, 1, 3, 5, 6, 8, 
swapping l:7 and r:3
2, 4, 3, 1, 7, 5, 6, 8, 
swapping l:8 and r:1
calling quickSort on 0 and 2
calling quickSort on 4 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:7 and r:1
2, 4, 3, 8, 1, 5, 6, 7, 
swapping l:7 and r:1
calling quickSort on 4 and 3
calling quickSort on 5 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:5 and r:1
2, 4, 3, 8, 7, 1, 6, 5, 
swapping l:5 and r:1
calling quickSort on 5 and 4
calling quickSort on 6 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
swapping l:6 and r:1
2, 4, 3, 8, 7, 5, 1, 6, 
swapping l:6 and r:1
calling quickSort on 6 and 5
calling quickSort on 7 and 7
2, 4, 3, 8, 7, 5, 6, 1, 
BUILD SUCCESSFUL (total time: 1 second)

我如何使算法与数据透视表一起用作任何索引 0 to a.length

Answer 1

您可以在开始排序之前简单地将所选的数据透视图与数组中的第一个元素交换，这样它将完全像以前一样工作。

int l = start;
int r = end;

this.swap(a, choosePivot(), start); 
int pivotIndex = start;