java - 快速排序方法给我一个 stackoverflowerror？

Question

我有一个快速排序方法，可以按升序对元素进行排序，但似乎不断出现 stackoverflowerror。

出于某种原因，当逻辑对我来说有意义时，它在 while 循环中显示错误。 这是快速排序类的代码:

    public T[] sort(T[] arr, int left, int right)
    {

        int l = left;
        int r = right;

        if (right <= left)
            return null;

        //Find the pivot in the middle
        T pivot = arr[(left + (right - left)) / 2];

        T temp;


        while (l <= r)
        {
            // check values on left are bigger than the pivot
            while (arr[l].compareTo(pivot) < 0)
            {
                l++;
            }
            // check if values are smaller than the pivot
            while (arr[r].compareTo(pivot) > 0)
            {
                r--;
            }

            // l and r have gone past each other swap them
            if (l <= r)
            {
                //swap process
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;

                // left pointer goes up 1
                // right pointer goes down 1
                l++;
                r--;
            }
        }

        if (left < r)
            sort(arr, left, r);
        if (l < right)
            sort(arr, l, right);
            return arr;
    }

错误好像是指向

//Find the pivot in the middle
    T pivot = arr[(left + (right - left)) / 2];

然后我似乎遇到了很多错误。

Answer 1

我相信您计算的 Pivot 不正确 你应该使用 T pivot = arr[left + (right - left)/2]; 下面是使用中间元素作为枢轴的快速排序程序:

public void quickSort(T arr[],int left, int right){
        int low =left, high = right;
        int pivot = arr[left + (right - left) / 2];

        while(low<=high){
            while (arr[low] < pivot) {
                low++;
            }

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

            if (low <= high) {
                int  temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;

                low++;
                high--;
            }

            if (left < high) {
                quickSort(arr,left, high);
            }

            if (low < high) {
                quickSort(arr,low, right);
            }
      }
}

希望对您有所帮助!!