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

本文介绍了更改我的quickSort算法Java中的数据透视的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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

这很好用，但是如果我将pivotIndex更改为让我们说int pivotIndex = end;，我会得到以下结果:

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)

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

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;