Get Started

• 选择排序
○ 遍历
○ 递归
• 快速排序
○ 每次取中间项，小左右大
• 归并排序
○ 左右两边分别排序再组合
• 计数排序
哈希表，将大小分配到顺序key中排列
• 了解其他四种排序（冒泡插入希尔基数）

算法要明白如何排序，而且必须要动手写，就算看了答案，自己写的时候也会出错。

选择排序

递归都可以用循环重写
• 代码

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

• 用循环重写

let sort = (numbers) => {
  for(let i=0; i<???; i++){
    let index = minIndex(numbers) // 需要修改
    // index是当前最小数的下标
    // index对应的数应该放到i处
    swap(numbers, index, i) // swap还没实现
    // index、i都是index的意思，建议i改名
  }
}

• 注意：实现swap就是将数组的对应下标的值交换（注意需要将对象也传进去）
• 错误的实现swap

let swap = (a, b) => {
  let temp = a
  a = b
  b = temp
}

swap(numbers[1], numbers[2])
发现numbers[1]和numbers[2]的值不变，因为a，b是简单类型，传参时会只传值
而numbers时对象，传参时传地址
• minIndex查找范围有问题

    ○ let index = minIndex(numbers.slice(i)) + i

• 代码

let sort = (numbers) => {
  for(let i=0; i<(numbers.length - 1); i++){
  let index = minIndex(number.slice(i))+i
  if(index != i){ swap(numbers, index, i) }
  }
  return numbers
}
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[index];i++ ){
    if( numbers[i] < numbers[index] ){
      index = i
    }
  }
  return index
}

快速排序（quick sort）

• 快排源码

let quickSort = arr =>{
  if (arr.length <= 1){ return arr; }
  let pivotIndex = Math.floor(arr.length/2)
  let pivot = arr.splice(pivotIndex)[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))
}

• arr.splice(pivotIndex)[0]
splice返回的是一个数组，然后[0]取它的第一项的值

归并排序（merge sort）

• 递归思路
左边一半排好序，右边一半排好序，然后左右合并（merge）起来。
• 归并排序源码

let quickSort = arr =>{
  if (arr.length <= 1){ return arr; }
  let pivotIndex = Math.floor(arr.length/2)
  let pivot = arr.splice(pivotIndex)[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))
}

计数排序（counting sort）

• 思路
用一个哈希表做记录
发现数字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)
      }
    }
  }
  rerurn result
}

注意：i in hash是看值与key是否一致
• 特点
• 数据结构不同
使用了额外的hashTable
只遍历数组一遍（+遍历一次hashTable）
这叫做【用空间函数见】
• 时间复杂度对比
选择排序 O(n^2)
快速排序 O(n log2 n)
归并排序 O(n log2 n)
计数排序 O(n+max)

还有哪些排序算法

• 冒泡排序
下标循环从1开始，该下标所属值两两对比，越大的往后排
https://visualgo.net/zh/sorting
• 插入排序
洗牌算法，遍历下标，将该下标与前一位对比，小的往前互换直到没有比他还大的数。
• 希尔排序
http://sorting.at/
• 基数排序
适合多位数排序。先从个位数排序，然受十位，百位，千位等

排序算法-选择快速归并计数