我使用数组中的第一个元素作为枢轴实现了一个有效的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;得到以下结果:
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
0 to a.length
您可以在开始排序之前简单地将所选的数据透视图与数组中的第一个元素交换,这样它将完全像以前一样工作。
int l = start; int r = end; this.swap(a, choosePivot(), start); int pivotIndex = start;