這個QuickSort實現有什麼問題？

我有以下：這個QuickSort實現有什麼問題？

function quickSort(array, low, high) { 
    var len = array.length, 
     l = low || 0, 
     r = high || len - 1, 
     m = Math.round((l + r)/2), 
     t; 

    do { 
     while (array[l] < array[m]) { 
      l += 1; 
     } 
     while (array[r] > array[m]) { 
      r -= 1; 
     } 

     if (l <= r) { 
      if (l < r) { 
       t = array[r]; 
       array[r] = array[l]; 
       array[l] = t; 

       console.log('Swapped ' + array[r] + ' with ' + 
             array[l] + '. ' + 
             array); 
      } 

      l += 1; 
      r -= 1; 
     } 
    } while (l <= r); 

    if (r > 0) quickSort(array, 0, r); 
    if (l < len - 1) quickSort(array, l, len - 1); 
}

使用，如下所示：

var initial = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10], // Duplicate, just to compare 
    sorted = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10]; 

quickSort(sorted); 

console.log('Initial: ' + initial + '\nSorted: ' + sorted);

令人驚訝地，代碼拋出stack_overflow陣列進行了排序之後。我想我錯過了遞歸退出條件，但我不知道在哪裏。

來源

2011-10-24 Lapple

您是否嘗試過手動排序列表（手工）並查看「交換」日誌行是否匹配。也許你可以給代碼添加一些註釋（例如爲什麼你有兩個幾乎相同的if嵌套？）。 – Lycha

@Lycha，是的，交換週期匹配。當我們到達'if（l <= r）'條件時，這意味着我們在'l'eft側有一個大於分隔元素'm'的元素。同樣，我們也有一個小於'm'的元素'r'。因此，我們交換它們，除非它們相等，並增加（和減少）走廊邊緣。 – Lapple

編輯（取代以前的答案）：我相信這裏的問題是你設置len變量的方式。對於原地排序，len應該只是被排序的數組部分的長度，而不是整個數組的長度，否則最後的比較永遠不會計算爲false。因此，而不是：

var len = array.length, 
    l = low || 0, 
    r = high || len - 1;

您需要根據l和r設置len：

var l = low || 0, 
    r = high || array.length - 1, 
    len = r-l;

你可以看到這裏的工作的jsfiddle：http://jsfiddle.net/nrabinowitz/PPeh9/6/ - 我有一個用於測試的隨機陣列更換您的測試數據。

來源

2011-10-24 18:23:28 nrabinowitz

不，在這種情況下，數組的右半部分根本不會被排序 - 在「do ... while」循環的末尾，「l」將等於「m-1」或「m」。你可以在提供的小提琴中檢查它 - 部分排序的數組在9之後有8個。 – Lapple

@Honneykeepa - 你是對的，先生。我會再看看這個 - 我認爲這就是邏輯關閉的地方。 – nrabinowitz

@Honneykeepa - 查看我的更新回覆。這裏的邏輯*是關閉的，但是這是因爲「len」被設置了，而不是你所比較的。 – nrabinowitz

這個QuickSort實現有什麼問題？

回答

相關問題