为什么这个 QuickSort Partition 方法是错误的？

Question

我有一个快速排序分区方法。但是我不明白为什么它是错误的

方法在这里：

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] 这是错误的.. .

Answer 1

第一行，

int pivotIndex = (first + last) / 2;

pivotIndex 现在占据中间元素的位置。

E pivot = list[pivotIndex];

现在您将该值分配给主元。

也许这就是您的代码给出错误答案的原因。

它只是将小于50的元素（即中间元素）放在左边，较大的元素放在右边。

为什么这个 QuickSort Partition 方法是错误的？

Why this QuickSort Partition method is wrong?

java

sorting

quicksort