排序算法

• 选择排序：每次选择最小的排第一个，然后数组concat连接后面的，可以用递归。递归出口：arr.length === 2
  时间复杂度：O(n^2)

let  sort = (numbers) => {
  if(numbers.length > 2){
    let index = minIndex(numbers)
    let min = numbers[index]
    numbers.splice(index,1)
    return [min].concat(sort(numebrs))
  }else{
     return number[0]<numbers[1] ? numbers : numbers.reverse
  }
}

• 快速排序：以某某为基准，小的去前面，大的去后面，重复即可。递归出口：arr.length < =1
  时间复杂度：O(n log2 n)

let quickSort = arr => {
  if(arr.length<=1){return arr}
  let pivotIndex = Math.floor(arr.length / 2)
  let pivot = arr.splice(pivotIndex,1)[0]
  let left = []
  let right = []
  for(let i = 0;i< arr.length;i++){
     if(arr[i] < pivot){ left.push(arr[i]) }
     else{ right.push[arri] }
  }
  return quickSort(left).concat([pivot],quickSort(right))
}

• 归并排序：左边一半排好序，右边一半排好序，然后合并起来，然后重复上述操作。递归出口：arr.length === 1
  时间复杂度：O(n log2 n)

let mergeSort = arr =>{
  let k = arr.length
  if(k===1){return arr}
  let left = arr.slice(0, Math.floor(k/2))
  let right = arr.slice(Math.floor(k/2))
  return merge(mergeSort(left), mergeSort(right))
}
let merge = (a, b)
  if(a.length === 0) return b
  if(b.length === 0) return a
  return a[0] > b[0] ?
  [b[0]].concat(merge(a, b.slice(1))) :
  [a[0]].concat(merge(a.slice(1), b))
}

• 计数排序：使用hash表
  时间复杂度：O(n+max)

let countSort = arr => {
  let hashTable = {},max = 0,result = []
  for(let i=0;i<arr.length;i++){
    if(!(arr[i] in hashTable)){
      hashTable[arr[i]] = 1  
    }else{
      hashTable[arr[i]] += 1
    }
    if(arr[i]>max){ max = arr[i] }
  }
  for(let j=0;j<max;j++){
    if(j in hashTable){
      for(let i=0;i<hashTable[j];i++){
         result.push[j]
      }
    }
  }
 return result
}