混合快速排序+插入排序java.lang.StackOverflowError的

Question

我试图计算混合快速排序的运行时间 - 插入排序。然而，当具有较大的阵列（500K〜元素）介绍，得到了一个java.lang.StackOverflowError的。我能以某种方式解决这个？不使用递归是不是一种选择。

下面的代码：

public class QuickSort2 {

private static void swap(int[] arr, int x, int y){
       int temp = arr[x];
       arr[x] = arr[y];
       arr[y] = temp;
    }

private static int partition(int[] arr, int lo, int hi){
    int pivot = arr[hi];
    int index = lo - 1;
    for(int i = lo; i < hi; i++){
        if(arr[i] < pivot){
            index++;
            swap(arr, index, i);
        }
    }
    swap(arr, index + 1, hi);
    return index + 1;
} 

public static void quickSort(int[] arr, int lo, int hi){
    if(lo < hi && hi-lo > 10){
        int q = partition(arr, lo, hi);
        quickSort(arr,lo,q-1);
        quickSort(arr,q+1,hi);
        }else{
            InsertionSort.insertSort(arr);
        }    
    }
}

而且，在插入排序：

public class InsertionSort {

static void insertSort(int[] arr){
    int n = arr.length;
    for (int j = 1; j < n; j++){
        int key = arr[j];
        int i = j-1;
        while ((i >= 0) && (arr[i] > key)){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
    }         
}

其中发生错误的行：

quickSort(arr,lo,q-1);
quickSort(arr,q+1,hi);

并调用代码：

public class RunningTime {

public static void main(String[] args) {
    int[] arr = ReadTest.readToArray("int500k");
    int lo = 0;
    int hi = arr.length - 1;

    long startTime = System.currentTimeMillis();
    QuickSort2.quickSort(arr, lo, hi);
    long stopTime = System.currentTimeMillis();
    long elapsedTime = stopTime - startTime;
    System.out.println("Running time: " + elapsedTime);
    System.out.println("Array is sorted: " + isSorted(arr));
}

}

Answer 1

您应该限制插入排序仅在数组的子集工作。

除此之外，我没有看到你的代码的任何其他问题。

在文件int500k排序？如果是这样，这是为快速排序，这意味着递归将是50万级深最坏的情况。

要解决它，你可以选择例如枢轴，而不是随机的arr[hi]。