我有一个quickSort分区方法。
但我不明白为什么这是错误的
方法在这里:
private static <E extends Comparable<E>> int partition(E[] list, int first, int last) {
int pivotIndex = (first + last) / 2;
E pivot = list[pivotIndex]; // Choose the first element as the pivot
swap(list, last, pivotIndex);
pivotIndex = last;
last--;
do {
// Search forward from left
while (first < last && list[first].compareTo(pivot) <= 0)
first++;
// Search backward from right
while (first <= last && list[last].compareTo(pivot) > 0)
last--;
// Swap two elements in the list
if (last >= first) {
swap(list, first, last);
first++;
last--;
}
} while (last > first);
swap(list, pivotIndex, first);
return first;
}
这是使用递归调用的方式:
quickSort ( array )
quickSortRec( array, 0, array.size - 1 )
quickSortRec (array, left, right)
pivotIndex = findpivot(array, left, right) //use any method
newPivotIndex = partition ( array, left, right, pivotIndex )
if ( newPivotIndex - left > 1 )
quickSortRec( array, left, newPivotIndex - 1 )
if ( right - newPivotIndex > 1 )
quickSortRec( array, newPivotIndex + 1, right )
我知道错误在于do while循环中,但我不知道为什么以及如何做。我不需要正确版本的分区方法...我只想知道为什么这是错误的。例如,如果我想对[12 28 79 19 60 22 3 50 75 60 25 97 98 12 88]进行排序,则会给我[3 12 19 22 25 12 28 50 60 60 75 79 88 97 98]这是错误的。 。
最佳答案
在第一行中
int pivotIndex = (first + last) / 2;
现在,pivotIndex保持中间元素的位置。
E pivot = list[pivotIndex];
现在,您将该值分配为透视。
也许这就是为什么您的代码给您错误的答案的原因。
它只是将小于50的元素(即中间元素)向左放置,向右放置较大。
关于java - 为什么此QuickSort分区方法错误?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33312464/