排序算法

1. 冒泡排序

1.1 基本思路

冒泡排序的过程，就是从第一个元素开始，重复比较相邻的两个项，若第一项比第二项更大，则交换两者的位置；反之不动

每一轮操作，都会将这一轮中最大的元素放置到数组的末尾。假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了

1.2 过程演示

// 对以下数组进行排序
[5, 3, 2, 4, 1]

// 将第一个元素5和它相邻的元素3作比较，发现5比3大，故交换
[3, 5, 2, 4, 1]
 ↑  ↑

// 将第二个元素5和第三个元素2作比较，发现5比2大，故交换
[3, 2, 5, 4, 1]
    ↑  ↑

// 将第三个元素5和第四个元素4作比较，发现5比4大，故交换
[3, 2, 4, 5, 1]
       ↑  ↑

// 将第四个元素5和第五个元素1作比较，发现5比1大，故交换
[3, 2, 4, 1, 5]
          ↑  ↑

// 我们继续从第一个元素3开始看起。比较3和2，发现3比2大，交换
[2, 3, 4, 1, 5]
 ↑  ↑

// 比较3和4，发现3比4小，符合从小到大排列的原则，故保持不动
[2, 3, 4, 1, 5]
    ↑  ↑

// 比较4和1，发现4比1大，交换
[2, 3, 1, 4, 5]
       ↑  ↑

// 比较4和5，发现4比5小，符合从小到大排列的原则，故保持不动
[2, 3, 1, 4, 5]
          ↑  ↑

// 从第一个元素2开始，比较2和3。发现2比3小，符合排序原则，故保持不动
[2, 3, 1, 4, 5]
 ↑  ↑

// 比较3和1，发现3比1大，交换
[2, 1, 3, 4, 5]
    ↑  ↑

// 比较3和4，发现3比4小，符合排序原则，故保持不动
[2, 1, 3, 4, 5]
       ↑  ↑

// 比较4和5，发现4比5小，符合排序原则，故保持不动
[2, 1, 3, 4, 5]
          ↑  ↑

// 从第一个元素2开始，比较2和相邻元素1，发现2比1大，交换
[1, 2, 3, 4, 5]
 ↑  ↑

// 接下来仍然会对剩余的元素进行相邻元素比较，但由于不再发生交换，故不再演示
[1, 2, 3, 4, 5]

每一次从头到尾的遍历都只能定位到一个元素的位置，因此元素有多少个，总的循环就要执行多少轮

1.3 编码实现

function bubbleSort(arr) {
    // 缓存数组长度
    const len = arr.length  
    // 外层循环用于控制从头到尾的比较+交换到底有多少轮
    for(let i=0;i<len;i++) {  
        // 内层循环用于完成每一轮遍历过程中的重复比较+交换
        for(let j=0;j<len-1;j++) {
            // 若相邻元素前面的数比后面的大
            if(arr[j] > arr[j+1]) {  
                // 交换两者
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    // 返回数组
    return arr
}

1.4 改进

随着外层循环的进行，数组尾部的元素会渐渐变得有序——当我们走完第1轮循环的时候，最大的元素被排到了数组末尾；走完第2轮循环的时候，第2大的元素被排到了数组倒数第2位；走完第3轮循环的时候，第3大的元素被排到了数组倒数第3位......依此类推，走完第 n 轮循环的时候，数组的后 n 个元素就已经是有序的

function betterBubbleSort(arr) {
    const len = arr.length  
    for(let i=0;i<len;i++) {
        // 注意差别在这行，我们对内层循环的范围作了限制
        for(let j=0;j<len-1-i;j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    return arr
}

1.5 进一步改进

最好的情况就是数组本来就是有序的

function betterBubbleSort(arr) {
    const len = arr.length  
    for(let i=0;i<len;i++) {
        // 区别在这里，我们加了一个标志位
        let flag = false
        for(let j=0;j<len-1-i;j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
                // 只要发生了一次交换，就修改标志位
                flag = true
            }
        }
        // 若一次交换也没发生，则说明数组有序，直接放过
        if(flag == false) 
            return arr
    }
    return arr
}

标志位可以帮助我们在第一次冒泡的时候就定位到数组是否完全有序，进而节省掉不必要的判断逻辑，将最好情况下的时间复杂度定向优化为O(n)，最坏时时间复杂度为O($n^2$)

2. 选择排序

2.1 基本思路

选择排序的关键字是“最小值”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止

2.2 过程演示

// 对以下数组进行排序
[5, 3, 2, 4, 1]

// 索引范围为[0,n-1]，即[0,4]之间的元素进行的遍历（两个箭头分别对应当前范围的起点和终点）
[5, 3, 2, 4, 1]
 ↑           ↑

// 得出整个数组的最小值为1。因此把1锁定在当前范围的头部，也就是和5进行交换
[1, 3, 2, 4, 5]

// 交换后，数组的第一个元素值就明确了。接下来需要排序的是[1,4]这个索引区间
[1, 3, 2, 4, 5]
    ↑        ↑

// 遍历这个区间，找出区间内最小值为2。因此区间头部的元素锁定为2，也就是把2和3交换相应地
[1, 2, 3, 4, 5]

// 将需要排序的区间范围的起点再次后移一位，此时区间为[2,4]
[1, 2, 3, 4, 5]
       ↑     ↑

// 遍历[2,4]区间，得到最小值为3。3本来就在当前区间的头部，因此不需要做额外的交换
[1, 2, 3, 4, 5]

// 依此类推，4会被定位为索引区间[3,4]上的最小值，仍然是不需要额外交换的
[1, 2, 3, 4, 5]

2.3 编码实现

function selectSort(arr)  {
  // 缓存数组长度
  const len = arr.length 
  // 定义 minIndex，缓存当前区间最小值的索引，注意是索引
  let minIndex  
  // i 是当前排序区间的起点
  for(let i = 0; i < len - 1; i++) { 
    // 这里len-1是因为遍历到最后一次的时候已经有序了
    // 初始化 minIndex 为当前区间第一个元素的索引
    minIndex = i  
    // i、j分别定义当前区间的上下界，i是左边界，j是右边界
    for(let j = i; j < len; j++) {  
      // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
      if(arr[j] < arr[minIndex]) {  
        minIndex = j
      }
    }
    // 如果 minIndex 对应元素不是目前的头部元素，则交换两者
    if(minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

时间复杂度为：O($n^2$)

3. 插入排序

3.1 基本思路

插入排序的核心思想是“找到元素在它前面那个序列中的正确位置”

具体来说，插入排序所有的操作都基于一个这样的前提：当前元素前面的序列是有序的。基于这个前提，从后往前去寻找当前元素在前面那个序列里的正确位置

3.2 过程演示

// 对以下数组进行排序
[5, 3, 2, 4, 1]

// 单个数字一定有序，因此数组首位的这个5可以看做是一个有序序列。在这样的前提下， 我们就可以选中第二个元素3作为当前元素，思考它和前面那个序列[5]之间的关系。很明显，3比5小，注意这里按照插入排序的原则，靠前的较大数字要为靠后的较小数字腾出位置
[暂时空出, 5, 2, 4, 1]
当前元素 3

// 再往前看，发现没有更小的元素可以作比较了。那么现在空出的这个位置就是当前元素3应该待的地方
[3, 5, 2, 4, 1]

// 当前元素变成了紧跟[3,5]这个有序序列的2。对比2和5的大小，发现2比5小。按照插入排序的原则，5要往后挪，给较小元素空出一个位置
[3, 暂时空出, 5, 4, 1]
当前元素 2

// 接着继续向前对比，遇到了3。对比3和2的大小，发现3比2大。按照插入排序的原则，3要往后挪，给较小元素空出一个位置
[暂时空出, 3, 5, 4, 1]
当前元素 2

// 此时2前面的有序序列已经被对比完毕了。我们把 放到最终空出来的那个属于它的空位里去
[2, 3, 5, 4, 1]

// 继续往下走，紧跟有序数组[2, 3, 5]的元素是4。仍然是从后往前，首先对比4和5的大小，发现4比5小，那么5就要为更小的元素空出一个位置
[2, 3, 暂时空出, 5, 1]
当前元素 4

// 向前对比，遇到了3。因为4比3大，符合从小到大的排序原则；同时已知当前这个序列是有序的，3前面的数字一定都比3小，再继续向前查找就没有意义了。因此当前空出的这个坑就是4应该待的地方
[2, 3, 4, 5, 1]

// 依此类推，最后一个元素1会被拱到[2, 3, 4, 5]这个序列的头部去，最终数组得以完全排序
[1, 2, 3, 4, 5]

几个关键点：

• 当前元素前面的那个序列是有序的
• “正确的位置”如何定义——所有在当前元素前面的数都不大于它，所有在当前元素后面的数都不小于它
• 在有序序列里定位元素位置的时候，是从后往前定位的。只要发现一个比当前元素大的值，就需要为当前元素腾出一个新的坑位

3.3 编码实现

function insertSort(arr) {
  // 缓存数组长度
  const len = arr.length
  // temp 用来保存当前需要插入的元素
  let temp  
  // i用于标识每次被插入的元素的索引
  for(let i = 1;i < len; i++) {
    temp = arr[i]  
    // j用于帮助 temp 寻找自己应该有的定位
    let j = i
    // 判断 j 前面一个元素是否比 temp 大
    while(j > 0 && arr[j-1] > temp) {
      // 如果是，则将 j 前面的一个元素后移一位，为 temp 让出位置
      arr[j] = arr[j-1]   
      j--
    }
    // 循环让位，最后得到的 j 就是 temp 的正确索引
    arr[j] = temp
  }
  return arr
}

• 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)
• 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O($n^2$)
• 平均时间复杂度：O($n^2$)