今日学习之二分法排序

二分法排序主要思想是在数组中截取一个数center，然后将数组分成leftArr、rightArr两部分，其中leftArr全部小于center，rightArr全部大于center（这里没有考虑有重复值的情况），最后递归leftArr和rightArr，如下图所示：

具体代码如下：

let arr = new Array(9, 4, 21, 5, 675, 3, 212, 43)
function dichotomySort(arr) {
  let len = arr.length
  if (len <= 1) return arr  // 此长度小于等于1的数组不能继续往下执行
  let leftArr = [],
    rightArr = []
  let middle = Math.floor((len - 1) / 2)
  let center = arr.splice(middle, 1)
  for (let i = 0; i < len - 1; i++) {
    let target = arr[i]
    target < center ? leftArr.push(target) : rightArr.push(target)
  }
  return dichotomySort(leftArr).concat(center, dichotomySort(rightArr))
}
let newArr = dichotomySort(arr)  //  [3, 4, 5, 9, 21, 43, 212, 675]

如有不对之处请多多指教，可发送邮箱[email protected]