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修改實現使用插入排序的短子陣列

回答

相關問題