Java快速排序算法

Question

我正在尝试学习快速排序算法，以下是我的代码:

import java.util.Arrays;

public class JavaFiddle {
    static int[] myArray = new int[]{35, 12, 25, 1, 5, 33, 56};

    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }

    public static void QuickSort(int[] array, int left, int right) {
        if (left < right) {
            int pivot = left + ((right - left) / 2);
            int index = partition(array, left, right, pivot);
            QuickSort(array, left, index - 1);
            QuickSort(array, index + 1, right);
        }
    }

    public static int partition(int[] array, int left, int right, int pivot) {
        while (left < right) {
            while (array[left] < pivot) {
                left++;
            }
            while (array[right] > pivot) {
                right--;
            }
            if (left < right) {
                swap(array, left, right);
                left++;
                right--;
            }
        }
        return left;
    }

    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

然而，这段代码给出了一个错误的结果：

[35, 12, 25, 1, 5, 33, 56] - before sort
[1, 12, 25, 35, 5, 33, 56] - after sort

我在这里错了什么？我找不到逻辑上的缺陷。

- Simeon Stoyanov

---

你尝试在QuickSort的开头添加一个println来打印left和right之间的子数组，这样你就可以找出发生意外情况的确切时间了吗？ - Stef

@Stef 没有人说其他的事情。让人们意识到他们沟通中的缺陷仍然很重要。成为程序员的一部分...就是要接受：所有细节都很重要。 - GhostCat

我已经意识到我的错误并编辑了帖子。是的，程序编译没有任何错误，我发现它只对数组的左侧部分进行排序，而不是右侧部分。如果这有助于您理解问题。 - Simeon Stoyanov

Answer 1

这里有多个错误，
你在主方法中定义了枢轴(pivot)，但快速排序算法会将枢轴从右侧元素交换到中间。 你在while循环中编辑左右值，在while循环中导致右边和左边比枢轴小/大，跳过了一些交换。
以下是没有你的 while { while { ... } } 和正确的枢轴(从右到中间)的正确实现。

import java.util.Arrays;
public class Main
{
    static int[] myArray = new int[] {35, 12, 25, 1, 5, 56, 33};
    public static void QuickSort(int[] array) {
        QuickSort(array, 0, array.length - 1);
    }
    public static void QuickSort(int[] array, int left, int right){
        if(left < right) {
            int index = partition(array, left, right);
            QuickSort(array, left, index - 1);
            QuickSort(array, index + 1, right);
        }
    }
    public static int partition(int[] array, int left, int right){
        int pivot = array[right];
        int first = left - 1;
        for (int j = left; j <= right - 1; j++) {
            if(array[j] < pivot) {
                first ++;
                swap(array, first, j);
            }
        }
        swap(array, first + 1, right);
        return first + 1;
    }
    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(myArray));
        QuickSort(myArray);
        System.out.println(Arrays.toString(myArray));
    }
}

另外，您将一个索引 pivot 与一个值 array[...] 进行了比较。

- IQbrod