JavaScript中的合併排序返回重複的元素

Question

我想在JS中進行合併排序，但不明白我在哪搞亂了。我希望這返回[1,2,3,4]，並返回[1,1,1,4]。

它的哪些部分需要更改？

var array = [3,2,1,4] 

function mergeSort(array) { 
    if (array.length === 1) { 
     return array 
    } else { 
     mid = Math.floor(array.length/2) 
     left = mergeSort(array.slice(0, mid)) 
     right = mergeSort(array.slice(mid, array.length)) 
     return merge(left, right) 
    } 
} 

function merge(left, right) { 
    var leftIndex = 0 
    var rightIndex = 0 
    var sorted = [] 

    while (leftIndex < left.length && rightIndex < right.length) { 
     if (left[leftIndex] <= right[rightIndex]) { 
      sorted.push(left[leftIndex]) 
      leftIndex += 1 
     } else { 
      sorted.push(right[rightIndex]) 
      rightIndex += 1 
     } 
    } 

    if (leftIndex < left.length) { 
     sorted = sorted.concat(left.slice(leftIndex)) 
    } else if (rightIndex < right.length) { 
     sorted = sorted.concat(right.slice(rightIndex)) 
    } 
    return sorted 
} 

console.log(mergeSort(array)) 

Answer 1

你有一個範圍的問題。您尚未聲明left，right和mid變量，因此將它們視爲隱式全局變量並導致混淆。

修正：

function mergeSort(array) { 
    if (array.length === 1) { 
     return array 
    } else { 
     var mid = Math.floor(array.length/2) 
     var left = mergeSort(array.slice(0, mid)) 
     var right = mergeSort(array.slice(mid, array.length)) 
     return merge(left, right) 
    } 
} 

Answer 2

它工作正常（有一些聲明和分號）。

var array = [3, 2, 1, 4], 
 
    result = mergeSort(array); 
 

 
function mergeSort(array) { 
 
    var mid, left, right; 
 
    if (array.length === 1) { 
 
     return array; 
 
    } else { 
 
     mid = Math.floor(array.length/2); 
 
     left = mergeSort(array.slice(0, mid)); 
 
     right = mergeSort(array.slice(mid, array.length)); 
 
     return merge(left, right); 
 
    } 
 
} 
 

 
function merge(left, right) { 
 
    var leftIndex = 0, 
 
     rightIndex = 0, 
 
     sorted = []; 
 

 
    while (leftIndex < left.length && rightIndex < right.length) { 
 
     if (left[leftIndex] <= right[rightIndex]) { 
 
      sorted.push(left[leftIndex]); 
 
      leftIndex += 1; 
 
     } else { 
 
      sorted.push(right[rightIndex]); 
 
      rightIndex += 1; 
 
     } 
 
    } 
 

 
    if (leftIndex < left.length) { 
 
     sorted = sorted.concat(left.slice(leftIndex)); 
 
    } else if (rightIndex < right.length) { 
 
     sorted = sorted.concat(right.slice(rightIndex)); 
 
    } 
 
    return sorted; 
 
} 
 

 
document.write('<pre>' + JSON.stringify(result, 0, 4) + '</pre>');