QuickSort修改实现使用插入排序的短子阵列

我想实现quickSort使用插入排序为短于一定长度的子数组。我已经写了这段代码，但问题是它可以用于多达400,000个整数的记录，但我需要使它运行5000,000个整数数组。它给我很难找到为什么我得到这个StackOverflow错误。QuickSort修改实现使用插入排序的短子阵列

public int[] quickSort2(int[] arrayOfIntegers, int startIndex, int endIndex) { 
    if (startIndex < endIndex) { 
     if (endIndex - startIndex < INSERTION_SORT_THRESHOLD) { 
      InsertionSort(arrayOfIntegers, startIndex, endIndex); 
     } else { 
      int pivotIndex = partition2(arrayOfIntegers, startIndex, endIndex); 
      quickSort2(arrayOfIntegers, startIndex, pivotIndex - 1); 
      quickSort2(arrayOfIntegers, pivotIndex + 1, endIndex); 
     } 
    } 
    return arrayOfIntegers; 
}

插入排序看起来像这样：

public int[] InsertionSort(int[] arrayOfNumbers, int startIndex, int endIndex) { 
    for (int i = startIndex + 1; i <= endIndex; i++) { 
     int key = arrayOfNumbers[i]; 
     int pointer = i - 1; 
     while (pointer >= startIndex && arrayOfNumbers[pointer] > key) { 
      arrayOfNumbers[pointer + 1] = arrayOfNumbers[pointer]; 
      pointer -= 1; 
     } 
     arrayOfNumbers[pointer + 1] = key; 
    } 
    return arrayOfNumbers; 
}

快速排序分区是：

private int partition2(int[] arrayOfIntegers, int start, int end) { 
    int pivot = arrayOfIntegers[end]; 
    int pointer = start - 1; 
    for (int i = start; i <= end - 1; i++) { 
     if (arrayOfIntegers[i] <= pivot) { 
      pointer += 1; 
      int temporaryStorage = arrayOfIntegers[i]; 
      arrayOfIntegers[i] = arrayOfIntegers[pointer]; 
      arrayOfIntegers[pointer] = temporaryStorage; 
     } 
    } 
    arrayOfIntegers[end] = arrayOfIntegers[pointer + 1]; 
    arrayOfIntegers[pointer + 1] = pivot; 
    return (pointer + 1); 
}

此外，当I CODE对尺寸5000,000整数数组并使用的子阵列运行快速排序长度3,6,9等排序整个数组，它不会给我“StackOverflow”错误。有人可以请帮忙

来源

2014-05-07 user16666

这是什么意思？ - '“使用长度为3,6,9”的子阵列。使用这些尺寸在哪里？ – Dukeling

非常重复 - [为什么这种快速排序导致堆栈溢出几乎排序列表和排序列表？]（http://stackoverflow.com/a/20255628） – Dukeling

你正确得到一个Stackoverflow，因为你的实现使用递归。您在quickSort2方法中调用quickSort2，这会在每次调用时增加堆栈。由于堆栈不能无限增长，因此您将获得一个Stackoverflow。

如果将阈值提高到3,6,9（依此类推），您将获得显着较少的递归（调用quickSort2）。这就是为什么你没有在这种情况下得到一个Stackoverflow。但它只是数组大小的问题。如果它足够大，无论如何你都会得到一个Stackoverflow。

解决方法是消除代码中的递归。消除递归不仅会避免一个Stackoverflow，它还会增加代码的速度，因为与迭代（Java）相比，递归要慢得多。

欲了解更多信息，请参阅http://www.geeksforgeeks.org/iterative-quick-sort/或Google iterative quicksort。

来源

2014-05-07 19:47:50

QuickSort修改实现使用插入排序的短子阵列

回答

相关问题