C++插入排序不適用於大型數組

-2

我的insertSort函數適用於小型數組，但不適用於具有50,000個隨機值的數組。我花了幾個小時試圖弄清楚這一點，但我很難過。這裏是代碼：C++插入排序不適用於大型數組

void insertionSort(int array[], int length) { 
    int swapHolder, counter, index; 
    for (counter = 1; counter < length; counter++) { 
     index = counter; 
     while (counter > 0 && array[index - 1] > array[index]) { 
       swapHolder = array[index]; 
       array[index] = array[index - 1]; 
       array[index - 1] = swapHolder; 
       index--; 
     } 
    } 
}

我的其他排序功能（bubbleSort）適用於大型數組，但我在這個問題上掛了。

來源

2016-07-05 Python guy

當你說「不行」時，你的意思是什麼？你能否請嘗試創建一個[最小，完整和可驗證示例]（http://stackoverflow.com/help/mcve）並向我們展示？並請[請閱讀如何提出良好問題]（http://stackoverflow.com/help/how-to-ask）。 –

爲什麼你遞減'索引'而不是增加它O_o – mangusta

......你爲什麼要檢查「counter> 0」，因爲這將永遠是真的？保證。 'counter'總是至少爲1，並且永遠不會遞減。這個問題的答案很簡單：「你的插入排序實現是錯誤的」。 –

線

while (counter > 0 && array[index - 1] > array[index]) {

應該

while (index > 0 && array[index - 1] > array[index]) {

在更深筆記，插入排序是O(n^2)所以平均的複雜性，它適用於小型陣列。也就是說，它不是排序50,000個值的正確算法。

來源

2016-07-05 01:39:39 aichao

那麼，BubbleSort也不是。我猜他只是試圖讓它正確，並且即使對於大型陣列，兩者都應該正常工作（雖然速度很慢）。 –

謝謝，這解決了我的問題。我的程序顯示它僅花費1828毫秒來分類50,000個值。 –

@RudyVelthuis這是一個課程項目，顯示各種排序/搜索方法的速度 –

C++插入排序不適用於大型數組

回答

相關問題