十种排序算法（1）

冒泡排序
思路：判断相邻元素的大小，交换位置，每次循环会得到在该次循环中最大的数，像气泡一样升到顶端，称为冒泡

//冒泡
    function fn1(arr) {
      for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            let a = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = a
          }
        }
      }
      return arr
    }

快速排序
思路：有些分治思想，从数组中随便取一个数为比较基准（我一般是取第一个），基准数左侧都比基准小，右侧都比基准大，然后再在左右两个区域重复上述步骤，直到所有元素都变得有序
递归法

//快排 递归版
    function fn2_recursion(arr) {
      let leftArr = []
      let rightArr = []
      let baseEl
      if (arr.length == 1 || arr.length == 0) {
        return arr
      }
      for (let i in arr) {
        if (i == 0) {
          baseEl = arr[0]
          continue
        }
        if (arr[i] >= baseEl) {
          rightArr.push(arr[i])
        } else {
          leftArr.push(arr[i])
        }
      }
      return [...fn2(leftArr), baseEl, ...fn2(rightArr)]
    }

递归法在没有递归思维的情况下，感觉很绕，熟练之后很简单，但是容易造成栈溢出
迭代版

//快排 迭代
    function fn2(arr) {
      let assistStack = [arr]
      while (assistStack.length < arr.length) {
        let baseEl
        let leftArr = []
        let rightArr = []
        for (let i of assistStack) {
          if (i.length !== 1) {
            for (let j in i) {
              if (j == 0) {
                baseEl = [i[0]]
                continue
              }
              if (i[j] >= baseEl) {
                rightArr.push(i[j])
              } else {
                leftArr.push(i[j])
              }
            }
            let index = assistStack.indexOf(i)
            if (leftArr.length !== 0) {
              assistStack.splice(index, 1, leftArr, baseEl)
              index += 2
            } else {
              assistStack.splice(index, 1, baseEl)
              index += 1
            }
            if (rightArr.length !== 0) {
              assistStack.splice(index, 0, rightArr)
            }
            //console.log(assistStack)
            break
          }
        }
      }
      //将结果合并
      for (let i in assistStack) {
        assistStack[i] = assistStack[i][0]
      }
      return assistStack
    }

迭代通常来说复杂的多，主要是状态的保存，万物皆有套路
插入排序
思路：将原数组分成左右两个区域，从右边拿出元素，与左边的区域比较，然后插入到正确的位置，左边区域从零开始扩张，右侧逐渐减小到零

//插排
    function fn3(arr) {
      let res = []
      for (let i in arr) {
        if (i == 0) {
          res.push(arr[i])
          continue
        }
        for (let j = 0; j < res.length; j++) {
          if (j == res.length - 1) {
            res.push(arr[i])
            break
          }
          if (arr[i] <= res[j]) {
            res.splice(j, 0, arr[i])
            break
          }
          if (arr[i] > res[j] && arr[i] <= res[j + 1]) {
            res.splice(j + 1, 0, arr[i])
            break
          }
        }
      }
      return res
    }

选择排序
思路：分成左右两个区域，遍历右侧区域，找到最小的push到左侧区域，和插入排序感觉好像，体感不同的是，插入排序对每个元素依次排序，选择排序不一定排哪个

//选择排序
    function fn4(arr) {
      let res = []
      let copyArr = arr.slice()

      for (let j = 0; j < arr.length; j++) {
        let min = Number(Infinity)
        let delIndex = -1
        for (let i in copyArr) {
          if (copyArr[i] < min) {
            min = copyArr[i]
            delIndex = i
          }
        }
        if(delIndex == -1){
          break
        }
        res.push(copyArr[delIndex])
        copyArr.splice(delIndex, 1)
      }
      return res
    }

归并排序
思路：分治思想，先分再治，字越少越抽象是真理

// 归并排序 递归
    function fn5_recursion(arr){
      let [l,r] = slice(arr)
      
      if(l.length > 1 || r.length > 1){
        return merge(fn5_recursion(l),fn5_recursion(r))
      }
      let res = merge(l,r)
      //console.log(res)
      return res

      function slice(arr){
        let sliceIndex = Math.floor(arr.length/2)
        let leftArr = arr.slice(0,sliceIndex)
        let rightArr = arr.slice(sliceIndex)
        //console.log(leftArr,rightArr)
        return [leftArr,rightArr]
      }
      function merge(leftArr,rightArr){
        let i = 0;
        let j = 0;
        let res = []       
        while(i < leftArr.length || j < rightArr.length){
          //console.log(res,'hahah',leftArr,rightArr)
          if(i == leftArr.length){
            res.push(rightArr[j])
            j++
            continue
          }
          if(j == rightArr.length){
            res.push(leftArr[i])
            i++
            continue
          }
          if(leftArr[i] < rightArr[j]){
            res.push(leftArr[i])
            i++
          } else {
            res.push(rightArr[j])
            j++
          }
          
        }
        //console.log(leftArr,rightArr,res)
        return res
      }
    }

今天先搞五种，明天续杯 奥利给