小五的算法系列 - 排序算法

Hello, 各位勇敢的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.

本人有丰富的脱发技巧, 能让你一跃成为资深大咖.

一看就会一写就废是本人的主旨, 菜到抠脚是本人的特点, 卑微中透着一丝丝刚强, 傻人有傻福是对我最大的安慰.

欢迎来到小五的算法系列之起航篇 - 排序算法.

此系列文章以《算法图解》和《学习JavaScript算法》两书为核心, 其余资料为辅助, 并佐以笔者愚见所成. 力求以简单、趣味的语言带大家领略这算法世界的奇妙. 此系列文章由浅入深, 逐一击破, 接下来我们用排序算法来开启这伟大航路的第一篇章.

本文讲解以下五种常见排序, 分别为三种简单排序: “冒泡排序”, “选择排序”, “插入排序” 和 两种复杂排序: “快速排序”, “归并排序”.

每种排序都通过 基本思想 、过程图解、算法分析、时间及空间复杂度、代码实现 五部分进行详细阐述.

<补充说明> 建议优先弄懂程序栈的执行顺序, 可阅读《算法图解 - 3.3 栈》, 会让学习快排和归并事半功倍; 此章主要用于理解递归的执行顺序, 笔者认为, 如果快排和归并理解困难, 归根结底是递归没有理解透彻; 此章节可为接下来的算法学习打好基石;【以上不影响本文阅读, 大家因人而异, 自行选择】

👺 基本思想: <相邻元素 两两对比找最大>

👺 过程图解:

👺 算法分析:

1. 外层循环: length - 1 次
2. 内层循环: length - 1 - 已确定元素个数(等同于外层循环的index) 次
3. 比对相邻元素大小, 若 arr[j] > arr[j + 1], 则互换元素

👺 复杂度:

根据上述分析, 外层循环 $n-1$ 次, 内层循环 $(n-1)/2$ 次, 故总执行次数为 $(n-1)^2 / 2$

tips: 时间复杂度及空间复杂度均不关心低阶变量、系数及常数

时间复杂度: 上述最高项为 $n^2$, 故时间复杂度为 $O(n^2)$

空间复杂度: 只有temp变量需要内存空间, 故空间复杂度为 $O(1)$

👺 代码实现:

const bubbleSort = (arr: number[]) => {
  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 temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

👺 基本思想: <依次选出最小值>

👺 过程图解:

👺 算法分析:

1. 外层循环: length - 1 次
2. 内层循环: 从 i + 1 处开始循环, 循环 length - (i + 1) 次
3. 记录外层循环 index 为 minIndex, 内层循环时, 若发现更小值, 更新 minIndex
4. 互换 arr[index] 和 arr[minIndex] 的位置

👺 复杂度:

根据上述分析, 外层循环 $n-1$ 次, 内层循环 $(n-1)/2$ 次, 故总执行次数为 $(n-1)^2 / 2$

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

空间复杂度: temp和minIndex变量需要内存空间, 因其不关心系数, 故为 $O(1)$

👺 代码实现:

const selectSort = (arr: number[]) => {
  let minIndex: number;

  for (let i = 0; i < arr.length; i++) {
    minIndex = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    
    let temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }

  return arr;
}

👺 基本思想: <从左至右 依次确认元素项位置>

👺 过程图解:

👺 算法分析:

1. 外层循环: 从1开始循环, 循环次数 length - 1
2. 内层循环: 从 j = i 开始循环, 逐一与前项比对, 小于前项则互换位置, 直到插入到正确的位置

👺 复杂度:

根据上述分析, 外层循环 $n-1$ 次, 内层循环 $n/2$ 次, 故总执行次数为 $n * (n - 1) / 2$

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

空间复杂度: 只有temp变量需要内存空间, 故为 $O(1)$

👺 代码实现:

const insertSort = (arr: number[]) => {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j - 1] > arr[j]) {
        let temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

👺 基本思想: <按基准值 左右分组后合并> (我们选取数组中间项为基准值)

👺 过程图解:

👺 算法分析:

1. 快速排序的思想是以一个值为基准, 小于基准值的推入左侧数组, 大于基准值的推入右侧数组; 递归调用, 直至数组为空; 将左右数组与基准值进行拼接, 全部拼接后形成所需数组;
2. 通过 splice 和 Math.floor(arr.length / 2) 来获取 middle 的值;
3. 理解程序栈的调用顺序, 可很好的理解快速排序;

👺 复杂度:

以基准值分半的递归过程复杂度为 $logn$; for循环的复杂度为 $n$

时间复杂度: $O(nlogn)$

空间复杂度: 空间复杂度即递归层数 -> $O(logn)$

👺 代码实现:

const quickSort = (arr: number[]): number[] => {
  if (!arr.length) return [];

  let leftArr: number[] = [];
  let rightArr: number[] = [];
  let middle = arr.splice(Math.floor(arr.length / 2), 1)[0];
  
  arr.forEach(item => {
    item < middle ? leftArr.push(item) : rightArr.push(item);
  })

  return quickSort(leftArr).concat(middle, quickSort(rightArr));
}

👺 基本思想: <将有序数组合并为更大的有序数组>

👺 过程图解:

👺 算法分析:

1. 归并排序用到的是分治思想, 即将原问题分解为子问题, 求解子问题后将子问题合并; 故将大数组分解为小数组, 直至数组中只有一个元素, 此时数组已全部有序, 将有序数组进行合并并排序, 形成新的有序数组, 全部合并后排序完成;
2. 通过 Math.floor(arr.length / 2) 来获取中间项索引, 通过索引及 slice 将数组一分为二;
3. 合并时, 比对左右数组的第一项, 将较小值推入新数组, 通过 shift 更新左右数组;
4. 理解程序栈的调用顺序, 可很好的理解归并排序;

👺 复杂度:

【分】二分操作 -> 复杂度为$logn$; 【合】while循环 -> 复杂度为$n$;

时间复杂度: $O(nlogn)$

空间复杂度: 空间复杂度为递归层数和临时数组所占空间 -> $logn+n$, 故空间复杂度为 $O(n)$

👺 代码实现:

const mergeSort = (arr: number[]): number[] => { // 拆分
  if (arr.length <= 1) return arr;

  let middle = Math.floor(arr.length / 2);
  let leftArr = arr.slice(0, middle);
  let rightArr = arr.slice(middle);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

const merge = (leftArr: number[], rightArr: number[]) => { // 合并
  let result: number[] = [];

  while (leftArr.length || rightArr.length) {
    if (leftArr.length && rightArr.length) {
      leftArr[0] < rightArr[0]
        ? result.push(leftArr.shift() as number)
        : result.push(rightArr.shift() as number);
    } else {
      if (leftArr.length) result.push(leftArr.shift() as number);
      if (rightArr.length) result.push(rightArr.shift() as number);
    }
  }

  return result;
}