各种排序

选择排序

即每次遍历数组选出一个最小的

                 an, n=1
pickSort(an) = {
                 [min(an)] + pickSort(an-1)

时间复杂度： n+(n-1)+(n-2)+(n-3)+...+1。约等于O(n^2)

selectSort = arr => {
    if(arr.length <= 1) return arr
    for(let i=0; i<arr.length-1; i++){ // 一共选择 length - 1 次，因为最后一次只有一个元素不用选
      let minIndex = i // 假设第一个是最小的
      for(let k=i+1; k<arr.length; k++){
          if(arr[k]<arr[i]){
              minIndex = k // 第 k 个比第一个小，就用 minIndex 记住 k
          }
      }
      [arr[i], arr[minIndex]] =  [arr[minIndex], arr[i]] // 交换 arr[i] 和 arr[minIndex] 的值
    }
    return arr
}

快速排序/归并排序/选择排序

• 分而治之: 把一个问题分解为两个相对简单的问题
• 降低规模：每次规模减少
• 对比：归并、快排、选择排序都有这些特点，只不过归并规模降低的最快（对半），快排次之（随机选择povit并不是对半），选择排序最后（一次一个）

计数排序

1. 把数字放入hash表，计算出现的次数
2. 遍历 1 ~ 最大值

特点：

• 空间换时间，时间复杂度O(n+max)
• 在某些情况下效率很低，元素个数少，值跨度大时，如[1,9999999,5555]

截图 (1).png

countSort = arr => {
    if(arr.length <= 1) return arr
    let hashTable = {} // 用于计数的对象
    let max = arr[0] // 用于记录最大值，假设第一个最大
    for(let i=0; i<arr.length; i++){
        const n = arr[i]
        hashTable[n] = hashTable[n] === undefined ? 1 : hashTable[n]+1 // n 对应的 value 要么置为1，要么加1
        if(n>max) max = n // 更新最大值
    }
    const result = [] // 要返回的数组
    console.log('hashTable')
    console.log(hashTable)
    for(let k=1; k<=max; k++){ // 正整数数组从1开始
        if(hashTable[k] !== undefined){ // hashTable[k] 表示数字出现的次数
            for(let m=0; m<hashTable[k]; m++){
                result.push(k) // 出现几次，就 push 几次
            }
        }
    }
    return result
}

冒泡排序

每次通过相邻元素两两对比来获取最大、最小值

时间复杂度： n+(n-1)+(n-2)+(n-3)+...+1。约等于o(n^2)

思路：类似于选择排序，但是是通过两两对比来选出最大或最小的一个，而选择排序是将每个元素和第一个元素对比。是一个相对低效的算法

bubbleSort = arr => {
  const {length} = arr
  for(let r=0; r<length-1; r++){
    for(let i=0; i<length-r-1; i++){
      if(arr[i]>arr[i+1]){
        [arr[i], arr[i+1]] = [arr[i+1], arr[i]] 
      }
    }
  }
  return arr
}

截图.png

插入排序

打牌时候用的排序，但是记住不要用splice，因为会导致整个数组后移，可以使用一一对比交换

复杂度：O(n^2)，最差情况是1+2+...+n-1+n

优化：二分查找。但插入会引起整体挪动，所以复杂度没有降低

insertSort = arr => {
  if(arr.length<=1)return arr
  for(let s=1; s<arr.length; s++){
    const n = arr[s] // 记住n
    let i // i要在for循环之后使用
    for(i=s-1; i>=0; i--){
      //比 n 大的数字往后挪了一位
      if(arr[i]>n) arr[i+1] = arr[i]
      // 遇到比 n 小的就中断循环
      else if(arr[i]<=n) break
    }
    arr[i+1] = n
  }
  return arr
}

总结

递归	非递归	利用hashTable	利用堆
归并排序	冒泡排序	计数排序	堆排序
快速排序	插入排序	桶排序
选择排序	希尔排序（一种高效的插入排序）	基数排序

算法	最坏时间复杂度	平均时间复杂度
归并排序	O(nlog2n)	O(nlog2n)
快速排序	O(n^2)	O(nlog2n)
选择排序	O(n^2)	O(n^2)
计数排序	O(n+max)	O(n+max)
冒泡排序	O(n^2)	O(n^2)
插入排序	O(n^2)	O(n^2)