在javascript中簡單實現合併排序

Question

以下實現合併排序算法時出現了什麼問題。它只是返回undefined。

我懷疑錯誤是在合併函數的某處。

有人可以幫我指出錯誤。

function mergeSort(arr1, lower, higher) { 

    if (lower < higher) { 
     var mid = Math.floor((lower + higher)/2); 
     mergeSort(arr1, lower, mid); 
     mergeSort(arr1, mid + 1, higher); 
     merge(arr1, lower, mid, higher); 
    } 
} 

和合並功能

function merge(arr1, lower, mid, higher) { 

    var i = lower; 
    var j = mid + 1; 
    var k = 0; 
    var mergearr = []; 

    while (i < j && j <= higher) { 

     if (arr1[i] <= arr1[j]) { 
      mergearr[k] = arr1[i]; 
      k++; 
      i++; 
     } else { 
      mergearr[k] = arr1[j]; 
      k++; 
      j++; 
     } 

    } 

    if (i === j) { 
     while (j < higher) { 
      mergearr[k] = arr1[j]; 
      k++; 
      j++; 
     } 
    } else if (j > higher) { 
     while (i < j) { 
      mergearr[k] = arr1[i]; 
      k++; 
      i++; 
     } 
    } 


    for (var a = 0; a <= k; a++) { 
     console.log(a); 
     arr1[a] = mergearr[a]; 
     console.log(arr1[a]); 
    } 

    return arr1; 
} 

這裏是控制檯

index: 0 
value: 4 
index: 1 
value: 5 
index: 2 
value: 4 
index: 3 
value: undefined 
index: 0 
value: 4 
index: 1 
value: 4 
index: 2 
value: 5 
index: 3 
value: 4 
index: 4 
value: undefined 
index: 0 
value: undefined 
index: 1 
value: 4 
index: 2 
value: undefined 
index: 3 
value: undefined 
index: 0 

Answer 1

撇開可能的「減1」中的排序錯誤，merge()功能有一個輸出問題在於它將合併列表複製回源數組。該函數被告知從lower合併到higher。但是，然後，合併的陣列被複制回從索引0開始的原始陣列。相反，你需要確保原始數組只lower和higher之間修改：

for (var a = 0; a <= k; a++) { 
    console.log(a); 
    arr1[a + lower] = mergearr[a]; // <--- here 
    console.log(arr1[a + lower]); 
} 

Answer 2

我可以調整你的代碼。是的，問題出在您的merge()功能。請看：

• 你並不需要，因爲沒有任何地方使用這個值 返回從merge()什麼。
• a應該lower時遞增，每次在 爲了避免重寫已經開始排序的數組
• 您的施工拿起奇indexes`價值的一部分是怪異和 腹脹
• 也搞砸指標在功能

var arr = [5,3,7,8,1,2,6,3,2]; 
 

 
mergeSort(arr, 0, arr.length - 1); 
 
console.log(arr); 
 

 
function mergeSort(arr, lower, higher) { 
 
    if (lower < higher) { 
 
     var mid = Math.floor((lower + higher)/2); 
 
     mergeSort(arr, lower, mid); 
 
     mergeSort(arr, mid + 1, higher); 
 
     merge(arr, lower, mid, higher); 
 
    } 
 
} 
 

 
function merge(arr, lower, mid, higher) { 
 
    var l = mid-lower+1, r = higher-mid, k = lower, mergearr = [], i = 0, j = 0; 
 

 
    while (i < l && j < r) { 
 
     if (arr[lower+i] <= arr[mid+j+1]) { 
 
      mergearr[k] = arr[lower+i]; i++; 
 
     } else { 
 
      mergearr[k] = arr[mid+j+1]; j++; 
 
     } 
 
     k++; 
 
    } 
 

 
    while (j < r) { 
 
     mergearr[k] = arr[mid+j+1]; k++; j++; 
 
    } 
 
    while (i < l) { 
 
     mergearr[k] = arr[lower+i]; k++; i++; 
 
    } 
 
    //console.log(mergearr, k, lower); 
 
    for (var a = lower; a < k; a++) { 
 
    arr[a] = mergearr[a]; 
 
    } 
 
}

的開始