Java 快速排序算法 [英] Java QuickSort algorithm

问题描述

我正在尝试学习快速排序算法，这是我目前的代码:

I am trying to learn Quick Sort algorithm and this is my code so far:

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));
    }
}

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

However, this code gives me an incorrect result:

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

我这里有什么问题?我找不到逻辑上的缺陷.

What do I have wrong here? I cannot find the flaw in the logic.

推荐答案

此处出现多个错误，
您在 main 方法中定义了枢轴，但快速排序算法会将枢轴从右侧元素交换到中间元素.您可以在 while 循环中编辑 while 循环中的左右值，这会导致左右值比枢轴小/高，并跳过一些交换.
这是没有您的 while { while { ... } } 和正确的枢轴(从右到中间)

Multiple errors here,
You define pivot in main method, but quick sort algorithm will swap pivot from right element to the middle. You edit left and right values in your while loop in a while loop, which result right and left to be smaller/taller than your pivot and skipping some swaps.
Here's the correct implementation without your while { while { ... } } and a correct pivot (from right to middle)

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[...] 的索引，array[...] 是一个值

Also you compare pivot which is an index with array[...] which is a value

这篇关于Java 快速排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！