递归思路

不以某谋为基准

想象你是一个体育委员
你面对的同学为[12,3,7,21,5,9,4,6]
左边一半自己排好序，右边一半自己排好序
然后左右两边各抽一个依次对比排序
至于左右两边怎么自己排好序的
只要递归一直分半到剩一个就行了
然后从一个并两个、四个、八个并起来
所有的合并排好的序都是体育委员比较的
image.png

  1. let mergeSort = arr => {
  2.   let k = arr.length
  3.   if(k === 1){return arr}
  4.   let left = arr.slice(0, Math.floor(k/2))
  5.   let right = arr.slice(Math.floor(k/2))
  6.   return merge(mergeSort(left),mergeSort(right)) 
  7.   //将左右两边合并
  8. }
  9. //合并
  10. let merge = (a,b) => {
  11.   if(a.length === 0) return b
  12.   if(b.length === 0) return a
  13.   return a[0] > b[0] ? 
  14.    [b[0]].concat(merge(a, b.slice(1))) : 
  15.    [a[0]].concat(merge(a.slice(1), b))
  16. };

image.png

  1. a[0] > b[0] 
  2.   ? [b[0]].concat(merge(a, b.slice(1)))
  3.     : [a[0]].concat(merge(a.slice(1), b))

这句代码的意思是，将a中最小的和b中最小的进行比较，把更小放到前面，然后再拼上剩下的归并的数组，直到a,b的长度为0
image.png

  1. let mergeSort = arr => {
  2.   let k = arr.length
  3.   if(k === 1){return arr}
  4.   let left = arr.slice(0, Math.floor(k/2))
  5.   let right = arr.slice(Math.floor(k/2))
  6.   return merge(mergeSort(left),mergeSort(right)) 
  7.   //将左右两边合并
  8. }
  9. //合并
  10. let merge = (a,b) => {
  11.   if(a.length === 0) return b
  12.   if(b.length === 0) return a
  13.   if(a[0] > b[0]){
  14.     let a1 = merge(a, b.slice(1))
  15.     a1.unshift(b[0])
  16.     return a1
  17.   }else{
  18.     let b1 = merge(a.slice(1), b)
  19.     b1.unshift(a[0])
  20.     return b1
  21.   }
  22. };

nima