java - QuickSort Java 实现问题

Question

我正在尝试将 QuickSort 算法实现为大学的家庭作业，但我只是无法理解我的代码中哪里有错误。我想这是一个逻辑错误，我想我错误地交换了我的支点。我真的需要一些帮助，在此先感谢您。有代码:

public class QuickSort {
    private int [] array;

    public QuickSort(int [] array){
        this.array = array;
    }

    public void sort(){
        partition(0, array.length - 1);
    }

    public void partition(int start, int end){
        if (end - start < 2){
            return;
        }
        int pivot_index = end;
        int i = start;
        int j = end - 1;
        while (i < j){
            //both elements are not in the right place
            if(array[i] > array[pivot_index] && array[j] <= array[pivot_index]){
                swap(array, i, j);
                i++;
                j--;
            }
            //the element on the left is not in place
            else if (array[i] > array[pivot_index] && array[j] > array[pivot_index]){
                j--;
            }
            //the element on the right is not in place
            else if (array[i] < array[pivot_index] && array[j] < array[pivot_index]){
                i++;
            }
            //both elements are in place
            else {
                i++;
                j--;
            }
        }
        if (array[i] > array[pivot_index]){
            swap(array, pivot_index, i);
            pivot_index = i;
        }
        partition(start, pivot_index - 1);
        partition(pivot_index + 1, end);
    }

    private static void swap(int [] tab, int index1, int index2){
        int temp = tab[index1];
        tab[index1] = tab[index2];
        tab[index2] = temp;
    }
}

Answer 1

方案一

想法是遍历数组以检查当前元素是否小于最后一个元素(基准)，如果是，则与第一个不是的元素交换(索引为 lastSmaller + 1)。

private void partition(int start, int end) {
    if (start >= end) {
        return;
    }

    int lastSmallest = start - 1;
    for (int i = start; i < end; i++) {
        if (array[i] < array[end])
            swap(++lastSmallest, i);
    }

    swap(++lastSmallest, end);
    partition(start, lastSmallest - 1);
    partition(lastSmallest + 1, end);
}

方案二

我想这就是你想要实现的。遍历数组，跳过左边和右边合适位置的所有元素。在错误的地方交换两者。

    private void partition(int start, int end) {
        if (end <= start) {
            return;
        }
        int k = end;
        int i = start;
        int j = end - 1;
        while (i < j) {
            // left is in place
            while (i < j && array[i] < array[k]) {
                i++;
            }
            // right is in place
            while (i < j && array[j] >= array[k]) {
                j--;
            }

            // both are not good
            if (i < j) {
                // swap
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;

                i++;
                j--;
            }
        }

        // swap left and pivot
        if (array[i] >= array[k]) {
            int temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
        partition(start, i - 1);
        partition(i + 1, end);
}

您的解决方案不起作用的原因是，当您发现两者都没有到位时，您将它们交换并继续对数组的其余部分进行分区。但是，你不能保证你交换的东西不违反规则。因此，您需要先跳过两侧的所有元素，然后再交换。