关于前端:小五的算法系列-排序算法

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;
}