Mcbai

JS编程: 归并排序

那么它如何工作?

``````[1, 5, 3, 9, 6, 4, 8]
``````
``````[1, 5, 3, 9] | [6, 4, 8]
``````
``````[1, 5] | [3, 9] [6] | [4, 8]
``````
``````[1] | [5] [3] | [9] [4] | [8]
``````

``````[9, 3, 6, 4]
``````
``````[9, 3] | [6, 4]
``````
``````[9] | [3] [6] | [4]
``````
``````[3, 9] | [4, 6]
``````
``````[3, 4, 6, 9]
``````

``````// Split the array into halves and merge them recursively

function  mergeSort (arr) {

if (arr.length  ===  1) {

// return once we hit an array with a single item

return arr

}

const middle =  Math.floor(arr.length  /  2) // get the middle item of the array rounded down

const left =  arr.slice(0, middle) // items on the left side

const right =  arr.slice(middle) // items on the right side

return  merge(

mergeSort(left),

mergeSort(right)

)

}

// compare the arrays item by item and return the concatenated result

function  merge (left, right) {

let result = []

let indexLeft =  0

let indexRight =  0

while (indexLeft <  left.length  && indexRight <  right.length) {

if (left[indexLeft] < right[indexRight]) {

result.push(left[indexLeft])

indexLeft++

} else {

result.push(right[indexRight])

indexRight++

}

}

return  result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))

}

const list = [2, 5, 1, 3, 7, 2, 3, 8, 6, 3]

console.log(mergeSort(list)) // [ 1, 2, 2, 3, 3, 3, 5, 6, 7, 8 ]
``````

Programming with JS: