排序算法（下）

复习任意长度的数组排序

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

所有递归都可以改写成循环
目前的minIndex

let minIndex = (numbers) => {
  numbers.indexOf(min(numbers))
let min = (numbers) => {
  return min(
    [numbers[0], min(numbers.slice(1))]
  )
}

写为循环

let minIndex = (numbers) => {
  let index = 0
  for(let i=1; i<numbers.length; i++){
    if(numbers[i] < numbers[index]){
      index = i
    }
  }
  return index
}

选择排序

每次找到最小的数放前面，然后对后面的数做同样的事情

let swap = (array,i,j) => {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
let minIndex = (numbers) => {
    let index = 0
    for(let i=1;i<numbers.length;i++){
        if(numbers[i] < numbers[index]){
            index = i
        }
    }
    return index
}
let sort = (numbers) => {
    for(let i=0; i< numbers.length -1; i++){
        let index = minIndex(numbers.slice(i))+i  //为什么要加i，因为slice以后下标从0开始计，所以要把slice掉的下标加回来
        if(index!==i){swap(numbers, index, i)}
    }
    return numbers
}

错误地实现 swap

let swap = (a, b) => {
    let temp = a
    a = b
    b = temp
}
swap(numbers[1], numbers[2])

你会发现，numbers[1] 和 numbers[2] 的值原封不动
因为 a b 是简单类型，传参的时候会复制值
而正确的 swap 中的 numbers 是对象，传参复制地址
这是传值 V.S. 传址的区别

发现bug用console.log大法调试

let sort = (numbers) => {
    for(let i=0; i< numbers.length -1; i++){
    console.log(`----`) //这个log用于分割每一次循环
    console.log(`i: ${i}`)
    let index = minIndex(numbers.slice(i))+ i
    console.log(`index: ${index}`)
    console.log(`min: ${numbers[index]}`)
    if(index!==i){
        swap(numbers, index, i)
        console.log(`swap ${index}: ${i}`)
        console.log(numbers)
    }
}
  return numbers
}

快速排序

通俗的说就是以某某为基准，小的去前面，大的去后面
重复这段话，就能排序

let quickSort = arr => {
    if (arr.length <= 1) { return arr }
    let pivotIndex = Math.floor(arr.length / 2)  //Math.floor向下取整
    let pivot = arr.splice(pivotIndex, 1)[0]  //为什么要写[0],如果不写返回的是被切掉的数组，所以提取数组中的第0个，才是我们需要的数字
    let left = []
    let right = []
    for (let i =0; i < arr.length; i++){
        if (arr[i] < pivot) { left.push(arr[i])
        } else { right.push(arr[i]) }
    }
    return quickSort(left).concat(
        [pivot], quickSort(right)
    )
}

归并排序

例如有一个数组[12, 3, 7, 21, 5, 9, 4, 6]
分成左边一半排好序，右边一半排好序
然后把左右两边合并(merge)起来
就变成了[3, 7, 12, 21]和[4, 5, 6, 9]
再分别比较两个数组的第0项，最小的提出来排前面，再把剩余的数组合并继续比较第0项

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))
}

计数排序

用一个哈希表作记录
发现数字 N 就记 N: 1，如果再次发现 N 就加1
最后把哈希表的 key 全部打出来，假设 N: m，那么 N 需要打印 m 次

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
}

其他的排序算法

冒泡排序
https://visualgo.net/zh/sorting
插入排序
https://visualgo.net/zh/sorting 点击 INS
希尔排序
http://sorting.at/ 自己选择 Shell Sort
基数排序
https://visualgo.net/zh/sorting 点击 RAD