以pivot为起始元素时的java快速排序问题

Question

我试了好几个小时。对于下面的代码，如果我们以6位数字的形式给出输入，{7,12,3,1,5,6}，但是对于这个输入，{7,12,3,1,5,6,2}；，它给出了一个堆栈溢出异常。请给我提个建议

package divideandconquer;

import utils.PrintUtil;

public class QuickSortLomatos_StartFromFirst {
    public void doSort(int[] arr, int start, int end) {
        if(start<end) {
            int pivotIndex = getPivot(arr, start, end);
                doSort(arr, start, pivotIndex - 1);
                doSort(arr, pivotIndex + 1, end);
        }
    }

    public int getPivot(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i=0, j=0;
        while(i<=j && j < end) {
            j++;
            if(arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, start, i);
        return i;
    }
    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{7, 12, 3, 1, 5, 6};
        QuickSortLomatos_StartFromFirst qs = new QuickSortLomatos_StartFromFirst();
        qs.doSort(arr, 0, arr.length - 1);
        PrintUtil.doPrint(arr);
    } 
}

Answer 1

在我找到的一个谷歌搜索中，解决方案是修改我的分区函数，如下所示

public int getPivot(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i=start+1, j=start+1;
        while(j<=(end)) {
            if(arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
            j++;
        }
        swap(arr, start, i-1);
        return i-1;
    }

我需要检查一下。。。我之前的流程，出了什么问题。Tku