合并排序實作JavaScript

我試圖在 JavaScript 中實作合并排序演算法，而沒有像 slice()、splice() 等內置方法。它并不完全符合我的意愿。你能幫我找出bug隱藏在哪里嗎？獲得輸出 [3, 5, 5, 3, 7] 而不是 [3, 5, 5, 7, 8]。

// Merge Sort implementation

// sort implementation
function sort(arr, start, mid, end) {

  // Creation and filling the temp arrays
  let lArray = [];
  let rArray = [];

  for (let i = 0; i <= mid - start; i  ) {
    lArray[i] = arr[start   i];
  }

  for (let j = 0; j <= end - mid - 1; j  ) {
    rArray[j] = arr[mid   1   j];
  }


  // Sorting and updating current array
  let i = 0;
  let j = 0;
  let k = start;

  while (i < lArray.length && j < rArray.length) {
    if (lArray[i] < rArray[j]) {
      arr[k] = lArray[i];
      i  ;
      k  ;
    } else {
      arr[k] = rArray[j];
      j  ;
      k  ;
    }
  }

  // Handling last element in lArray or rArray

  i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j];
}

// Recursive Merge Sort 
function recursiveMergeSort(arr, start, end) {
  if (start < end) {
    let mid = Math.floor(((end)   start) / 2);
    //console.log(start, end, mid);
    recursiveMergeSort(arr, start, mid);
    recursiveMergeSort(arr, mid   1, end);
    sort(arr, start, mid, end);
  }
}

function mergeSort(arr) {

  let start = 0;
  let end = arr.length - 1;

  recursiveMergeSort(arr, start, end);
  return (arr)
}

console.log(mergeSort([5, 8, 3, 7, 5]));

uj5u.com熱心網友回復：

// Handling last element in lArray or rArray 是不正確的。

合并陣列后，您必須檢查其余部分并復制未經處理的尾部（如果確實存在）

 while (i < lArray.length) {
     arr[k] = lArray[i];
     i  ;
     k  ;
 }
 while (j < rArray.length) {
     arr[k] = rArray[j];
     j  ;
     k  ;
 }

用此代碼替換三元運算子可為給定資料提供正確結果

uj5u.com熱心網友回復：

自頂向下歸并排序的優化版本示例。它對作業陣列進行一次性分配，并使用一對相互遞回的函式來改變每一級遞回的合并方向。在我的系統上對 100 萬個偽隨機整數進行排序大約需要 1/4 秒：

// merge sort top down

function merge(a, b, bgn, mid, end) {
  var i = bgn                           // left:  a[bgn,mid)
  var j = mid                           // right: a[mid,end)
  var k = bgn                           // index for b[]
  while(true){
    if(a[i] <= a[j]){                   // if left <= right
      b[k  ] = a[i  ]                   //   copy left
      if(i < mid)                       //   if not end of left
        continue                        //     continue back to while
      do                                //   else copy rest of right
        b[k  ] = a[j  ]
      while(j < end)
      break                             //     and break
    } else {                            // else left > right
      b[k  ] = a[j  ]                   //   copy right
      if(j < end)                       //   if not end of right
        continue                        //     continue back to while
      do                                //   else copy rest of left
        b[k  ] = a[i  ]
      while(i < mid)
      break                             //     and break
    }
  }
}

function sortatob(a, b, bgn, end) {     // sort a to b
  if ((end-bgn) < 2){
    b[bgn] = a[bgn]
    return
  }
  var mid = Math.floor(bgn   (end - bgn) / 2)
  sortatoa(a, b, bgn, mid)
  sortatoa(a, b, mid, end)
  merge(a, b, bgn, mid, end)
}

function sortatoa(a, b, bgn, end) {     // sort a to a
  if ((end-bgn) < 2)
    return
  var mid = Math.floor(bgn   (end - bgn) / 2)
  sortatob(a, b, bgn, mid)
  sortatob(a, b, mid, end)
  merge(b, a, bgn, mid, end)
}

function mergesort(a) {                 // entry function
  if(a.length < 2)
      return
  var b = new Array(a.length)           // allocate temp array
  sortatoa(a, b, 0, a.length)           // start with sort a to a
}

var a = new Array(1000000)
for (i = 0; i < a.length; i  ) {
  a[i] = parseInt(Math.random() * 1000000000)
}
console.time('measure')
mergesort(a)
console.timeEnd('measure')
for (i = 1; i < a.length; i  ) {
  if(a[i-1] > a[i]){
    console.log('error')
    break
  }
}

標籤：javascript 算法 排序 递归 归并排序

上一篇：使用python中的遞回將子序列存盤在串列串列中

下一篇：查找anxn矩陣行列式的程式不起作用