手写数据结构 排序算法 篇（上）

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
}

选择排序的时间复杂度
在时间复杂度这方面，选择排序没有那么多弯弯绕绕：最好情况也好，最坏情况也罢，两者之间的区别仅仅在于元素交换的次数不同，但都是要走内层循环作比较的。因此选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)。

function insertSort(arr) {
    // 缓存数组长度
    const len = arr.length
    // temp 用来保存当前需要插入的元素
    let temp
    // i用于标识每次被插入的元素的索引
    for (let i = 1; i < len; i++) {
        // j用于帮助 temp 寻找自己应该有的定位
        let j = i
        temp = arr[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
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
console.log(insertSort(arr));

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

function shellSort(arr) { // 参数为需要排序的数组
  // 获取初始的增量
  let gap = Math.floor(arr.length / 2);
  while (gap >= 1) { // 增量小于1时结束循环
    // 从gap开始遍历，因为插入排序假设第一个是有序的
    for (let i = gap; i < arr.length; i++) {
      let j = i; // 为插入排序从后向前排序提供条件
      // 如果排序的后面的数字小于前面的，交换两个数的位置
      while (arr[j] < arr[j - gap] && j - gap >= 0) {
        [arr[j], arr[j - gap]] = [arr[j - gap], arr[j]]
        // j减小gap从后向前遍历
        j -= gap;
      }
    }
    // 增量每次都减小一半
    gap = Math.floor(gap / 2);
  }
  return arr;
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
console.log(shellSort(arr));

时间复杂度
● (1) 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
● (2) 最坏情况：O(nlog2n)。
● (3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

function mergeSort(arr) {
    const len = arr.length
    // 处理边界情况
    if (len <= 1) {
        return arr
    }
    // 计算分割点
    const mid = Math.floor(len / 2)
    // 递归分割左子数组，然后合并为有序数组
    const leftArr = mergeSort(arr.slice(0, mid))
    // 递归分割右子数组，然后合并为有序数组
    const rightArr = mergeSort(arr.slice(mid, len))
    // 合并左右两个有序数组
    arr = mergeArr(leftArr, rightArr)
    // 返回合并后的结果
    return arr
}
function mergeArr(arr1, arr2) {
    // 初始化两个指针，分别指向 arr1 和 arr2
    let i = 0, j = 0
    // 初始化结果数组
    const res = []
    // 缓存arr1的长度
    const len1 = arr1.length
    // 缓存arr2的长度
    const len2 = arr2.length
    // 合并两个子数组
    while (i < len1 && j < len2) {
        if (arr1[i] < arr2[j]) {
            res.push(arr1[i])
            i++
        } else {
            res.push(arr2[j])
            j++
        }
    }
    // 若其中一个子数组首先被合并完全，则直接拼接另一个子数组的剩余部分
    if (i < len1) {
        return res.concat(arr1.slice(i))  // concat不会改变原数组
    } else {
        return res.concat(arr2.slice(j))
    }
}
let arr = [3, 4, 2, 8, 5, 5, 2, 0, 6, 6, 3]
console.log(mergeSort(arr));

我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次，因此就有 log(n) 轮。
 // 计算分割点
const mid = Math.floor(len / 2)    
// 递归分割左子数组，然后合并为有序数组
const leftArr = mergeSort(arr.slice(0, mid)) 
// 递归分割右子数组，然后合并为有序数组
const rightArr = mergeSort(arr.slice(mid,len))
因此单次切分对应的是常数级别的时间复杂度 O(1)。
再看合并，单次合并的时间复杂度为 O(n)。O(n) 和 O(1) 完全不在一个复杂度量级上，因此本着“抓主要矛盾”的原则，我们可以认为：决定归并排序时间复杂度的操作就是合并操作。
log(n) 轮对应 log(n) 次合并操作，因此归并排序的时间复杂度就是 O(nlog(n))。