在我的快速排序算法java中更改枢轴 [英] change pivot in my quickSort algorithm java

问题描述

I have implemented a working quickSort algorithm using the first element in the array as the pivot, that look like this:

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

And this works nicely, but if I change the pivotIndex to lets say int pivotIndex = end; I get this result:

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)

How to I make the algorithm work with the pivotIndex as any index 0 to a.length

解决方案

You could simply swap the pivot you chose with the first element in the array before you start sorting, that way it'll work exactly as before.

int l = start;
int r = end;

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

这篇关于在我的快速排序算法java中更改枢轴的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！