JavaScript Quicksort遞歸

Question

我試圖在JavaScript中爲int數組實現快速排序算法。 我的代碼有問題。前幾個ints得到很好的排序，但是在sortet數組的末尾總是有一個整數放置多次，儘管它在數組中只有一次應該排序。希望有人會發現我的錯。 謝謝。

function quicksort(array) { 
    var randomPlace = Math.round(Math.random() * array.length); 
    var pivotelement = array[randomPlace]; 
    left = new Array; 
    right = new Array; 
    for (var i = 0; i < array.length; i++) { 
     if (array[i] < pivot) { 
      left[left.length] = array[i]; 
     } else { 
      right[right.length] = array[i]; 
     } 
    } 
    if ((left.length == 0 || left.length == 1) && (right.length == 0 || right.length == 1)) { 
     return left.concat(right); 
    } else if (left.length == 0 || left.length == 1) { 
     return (left.concat((quicksort(right)))); 
    } else if (right.length == 0 || right.length == 1) { 
     return ((quicksort(left)).concat(right)); 
    } else { 
     return (quicksort(left)).concat((quicksort(right))); 
    } 
} 

Answer 1

我認爲您錯誤地識別了randomPlace。由於您使用的是Math.round()，因此它會返回undefined。初始化left當

此外，使用下面的代碼，right：

試試這個

var left = new Array(); 
var right = new Array(); 

你可以看到我的完整的小提琴here

Answer 2

除了一些nameming混亂，如pivotelement vs pivot和Math.round vs Math.floor，則需要解決例如[1, 1, 1]這個始終返回left = []和right = [1, 1, 1]的問題，該問題會無限次地調用quicksort([1, 1, 1])。

要解決此問題，您需要檢查空的left和right的每個元素，如果它等於隨機數據透視表。然後返回right，而不必再撥打quicksort。

function quicksort(array) { 
 
    var randomPlace = Math.floor(Math.random() * array.length), 
 
     pivot = array[randomPlace], 
 
     left = [], 
 
     right = [], 
 
     i; 
 

 
    for (i = 0; i < array.length; i++) { 
 
     (array[i] < pivot ? left : right).push(array[i]); 
 
    } 
 
    console.log(pivot, JSON.stringify(array), JSON.stringify(left), JSON.stringify(right)); 
 

 
    // prevent looping forever 
 
    if (!left.length && right.every(function (v) { return v === pivot; })) { 
 
     return right; 
 
    } 
 

 
    if (left.length <= 1 && right.length <= 1) { 
 
     return left.concat(right); 
 
    } 
 
    if (left.length <= 1) { 
 
     return left.concat(quicksort(right)); 
 
    } 
 
    if (right.length <= 1) { 
 
     return quicksort(left).concat(right); 
 
    } 
 
    return quicksort(left).concat(quicksort(right)); 
 
} 
 

 
console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

另一種解決方案是將陣列分成三個陣列，一個用於更小的值，一個用於相等的值和一個更大的值。然後只對較小和較大的數組進行排序。

function quicksort(array) { 
 
    var randomPlace = Math.floor(Math.random() * array.length), 
 
     pivotValue = array[randomPlace], 
 
     left = [], 
 
     pivot = [], 
 
     right = [], 
 
     i; 
 

 
    for (i = 0; i < array.length; i++) { 
 
     if (array[i] === pivotValue) { 
 
      pivot.push(array[i]); 
 
      continue; 
 
     } 
 
     (array[i] < pivotValue ? left : right).push(array[i]); 
 
    } 
 

 
    console.log(pivotValue, JSON.stringify(array), JSON.stringify(left), JSON.stringify(pivot), JSON.stringify(right)); 
 

 
    if (left.length <= 1 && right.length <= 1) { 
 
     return left.concat(pivot, right); 
 
    } 
 
    if (left.length <= 1) { 
 
     return left.concat(pivot, quicksort(right)); 
 
    } 
 
    if (right.length <= 1) { 
 
     return quicksort(left).concat(pivot, right); 
 
    } 
 
    return quicksort(left).concat(pivot, quicksort(right)); 
 
} 
 

 
console.log(quicksort([2, 7, 4, 8, 3, 11, 49, 20, 10, 1, 1, 1]));

.as-console-wrapper { max-height: 100% !important; top: 0; }