QuickSort 在线程 "main" java.lang.StackOverflowError 中给出异常

Question

我写了如下快速排序代码。排序以中间数为基准：

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] numbers = {3, 6, 9, 1, 34};

        int low = 0;

        int high = numbers.length - 1;

        quicksort(numbers, low, high);  

    }

    static void quicksort(int[] arr, int low, int high) {

        int i = low;
        int j = high;

        int middle = arr[(low + high) / 2];

        while(i < j) {      
            while(arr[i] < middle ) {
                i++;
            }

            while(arr[j] > middle) {
                j--;
            }

            if( i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }


        }

        if(low < j) {
            quicksort(arr, low, j);         
        }

        if(i < high) {
            quicksort(arr, i, high);
        }

        System.out.println(Arrays.toString(arr));

    }

}

但是，在运行代码之后，我遇到了 Whosebug 异常。它说 Exception in thread "main" java.lang.WhosebugError

Exception in thread "main" java.lang.WhosebugError
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)
    at QuickSort.quicksort(QuickSort.java:47)

请帮我找出上面代码运行中可能有什么问题。

Answer 1

i和j的值需要分别递增和递减。请参阅下面的工作代码：

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] numbers = {3, 9, 6, 1, 34};

        int low = 0;

        int high = numbers.length - 1;

        quicksort(numbers, low, high);  

    }

    static void quicksort(int[] arr, int low, int high) {

        int i = low;
        int j = high;

        int middle = arr[(low + high) / 2];

        while(i <= j) {      
            while(arr[i] < middle ) {
                i++;
            }

            while(arr[j] > middle) {
                j--;
            }

            if( i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
                j--;
            }


        }

        if(low < j) {
            quicksort(arr, low, j);         
        }

        if(i < high) {
            quicksort(arr, i, high);
        }

        System.out.println(Arrays.toString(arr));

    }

}

希望对您有所帮助！

Answer 2

您可以查看此 link 以更好地了解快速排序及其工作原理。

public static void quickSort(int[] arr, int low, int high) { 如果（arr == null || arr.length == 0） return;

        if (low >= high)
            return;


        int middle = low + (high - low) / 2;
        int pivot = arr[middle];


        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (arr[j] > pivot) {
                j--;
            }

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        // recursively sort two sub parts
        if (low < j)
            quickSort(arr, low, j);

        if (high > i)
            quickSort(arr, i, high);
    }

QuickSort 在线程 "main" java.lang.StackOverflowError 中给出异常

QuickSort giving exception in thread "main" java.lang.StackOverflowError

java

arrays

sorting

algorithm

quicksort