瞭解就地合併排序

我正在努力理解就地版本的合併排序。瞭解就地合併排序

function merge(left, right){ 
    var result = [], 
     il  = 0, 
     ir  = 0; 

    while (il < left.length &#038;&#038; ir < right.length){ 
     if (left[il] < right[ir]){ 
      result.push(left[il++]); 
     } else { 
      result.push(right[ir++]); 
     } 
    } 

    return result.concat(left.slice(il)).concat(right.slice(ir)); 
} 


function mergeSort(items){ 

    if (items.length < 2) { 
     return items; 
    } 

    var middle = Math.floor(items.length/2), 
     left = items.slice(0, middle), 
     right = items.slice(middle), 
     params = merge(mergeSort(left), mergeSort(right)); 

    params.unshift(0, items.length); 
    items.splice.apply(items, params); 
    return items; 
}

什麼是添加0和items.length到PARAMS前面的目的是什麼？我不明白items.splice.apply正在做什麼，但是從控制檯日誌記錄中看到一些例子，它看起來只是將沒有移動的東西移除到params。這是什麼原因？

來源

2016-09-10 AlanH

這不是就地。 – user2357112

@ user2357112我從中得到的代碼是https://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/。它說這是一個原地實施。 – AlanH

......博客文章正好解釋了* unshift和splice東西的作用。 – user2357112

TLDR：用排序後的版本替換items的內容。

Array.prototype.splice有the following signature：

array.splice(start, deleteCount[, item1[, item2[, ...]]])

它消除了deleteCount項目從指數start開始，以被提供的項目替換它們。

items.splice.apply(items, params)執行items.splice(...)，參數取自params。 params.unshift(0, items.length)後，params是

[0, items.length, sortedItem1, sortedItem2, ...]

使呼叫執行items.splice(0, items.length, sortedItem1, sortedItem2, ...)，刪除items.length項目從索引0（所以所有的）開始，在有序的項目替換它們。

來源

2016-09-10 03:21:47 user2357112

你能解釋爲什麼它不在位嗎？我沒有完全聽取您的意見。 – AlanH

@AlanH：它爲'result'，'slice'和'concat'使用了大量的輔助存儲。 – user2357112

瞭解就地合併排序

回答

相關問題