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

我在这里有什么问题？我找不到逻辑上的缺陷。

Answer 1

这里有多个错误，
您在 main 方法中定义了枢轴，但快速排序算法会将枢轴从右侧元素交换到中间元素。
您可以在 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[...] 的索引这是一个值