103.实现归并排序

[nanslee]

[2, 9, 1, 8, 3, 7]

[zlx362211854]

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序 如　设有数列{6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3； 第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4； 第三次归并后：{1,6,8,38,100,202,301},比较次数：4； 总的比较次数为：3+4+4=11；

var arr = [2, 9, 1, 8, 7, 3]
function lump(arr) {
var l = arr.length
var split = Math.ceil(l / 2)
var map = []
for (let i = 0; i < split; i++) {
map[i] = arr.slice(i * 2, i * 2 + 2).reduce((x, y) => x.concat(y), []).sort((a, b) => a - b)
}
console.log(map, 'map')
if (map.length === 1) {
return map[0]
} else {
return lump(map)
}
}
console.log(lump(arr), 'lump')

// 第一次归并 [[2, 9], [1, 8], [3, 7]] // 第二次归并 [[1, 2, 8, 9], [3, 7]] // 第三次归并 [1,2,3,7,8,9]

[goldEli]

const arr = [2, 9, 1, 8, 3, 7]

function mergeSort(arr) {

  const len = arr.length

  if (len < 2) return arr

  const midIndex = Math.floor(len/2)
  const left = arr.slice(0, midIndex)
  const right = arr.slice(midIndex)

  return merge(
    mergeSort(left), 
    mergeSort(right)
  )
}

function merge(left, right) {
  let arr = []
  while(left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      arr.push(left.shift())
    } else {
      arr.push(right.shift())
    }
  }
  if (left.length > 0) {
    arr = [...arr, ...left]  
  }
  if (right.length > 0) {
    arr = [...arr, ...right]
  }
  return arr
}

console.log(mergeSort(arr)) // [1,2,3,7,8,9]

[nanslee]

const merge = (l, r) => {
  let result = []
  let i = 0,
    j = 0
  while (i < l.length && j < r.length) {
    if (l[i] < r[j]) {
      result.push(l[i])
      i++
    } else {
      result.push(r[j])
      j++
    }
  }

  if (i < l.length) {
    result.push(...l.slice(i))
  } else {
    result.push(...r.slice(j))
  }

  return result;
}

const mergeSort = arr => {
  if(arr.length < 2) return arr;

  let m = Math.floor(arr.length / 2);
  let l = mergeSort(arr.slice(0, m));
  let r = mergeSort(arr.slice(m));

  return merge(l, r)
}

console.log(mergeSort([2, 9, 1, 8, 3, 7]))