排序算法总结

JavaScript实现十大排序算法，代码+动图+在实现代码的时候遇到的坑

冒泡算法

（1） 实现思路

不断的重复的对比相邻的两个元素，把大（小）的移到一个方向去

（2） 代码实现：

bubbleSort (arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
      for (let j = 0; j < len - i - 1; j++) {
        if (arr[j + 1] < arr[j]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        }
      }
    }
    return arr
  }

（3）写代码时候容易犯的思路错误：

在if (arr[j + 1] < arr[j]) 这块用 arr[j] 和 arr[i]做比较，
冒泡排序中，外圈循环只是用来计数的。需要做比较的是相邻的两项，就是arr[j] & arr[j + 1]

（4） 动画效果

冒泡排序.png

选择排序

（1） 实现思路

每一次直接选出最小（大）的一个，不断重复

seleteSort (arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
      let minIndex = i
      for (let j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIndex]) {
          [arr[minIndex], arr[j]] = [arr[j], arr[minIndex]]
          minIndex = j
        }
      }
    }
    return arr
  },

插入排序

  insertSort (arr) {
    let len = arr.length
    for (let i = 0; i < len; i++) {
      let index = i
      for (let j = i - 1; j >= 0; j--) {
        if (arr[j] > arr[index]) {
          [arr[j], arr[index]] = [arr[index], arr[j]]
          index = j
        }
      }
    }
    return arr
  },

快速排序

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