JS算法之常规排序算法

2022-08-25 14:53:42 浏览数 (1)

❝亚里士多德把知识分为三类: 第一类是「经验」，会做但不知道为什么这么做是对的； 第二类是知其然又知其所以然的「技术」，它来源于经验，是通过对经验的总结和归纳所形成的一般化理论； 第三类是没有用的、自己为自己而存在的知识就是科学 ❞

前言

大家好，我是柒八九。因为，最近在看Vue3 源码分析，发现无论React还是Vue，在框架层面，为了实现特定的场景，它们为我们封装了很多比较复杂的逻辑。比如，

  • 针对Virtual Dom的Diff算法中树的遍历(DSF);
  • 还有针对Vue3的双端Diff中在查看可复用节点时，用到的「最小递增子序列」算法；
  • 针对指定「DSL」(领域特定语言)的编译、转换处理中用到 stack数据结构进行token的匹配
  • 针对Vue中内置组件KeepAlive中用到的缓存中用到的「LRU」(最近最久未使用)
  • 等等

「透过现象看本质」，无论是如何高深的算法或者思路，其实都是利用合适的数据结构对其遍历和筛选处理。而今天我们就来利用一篇文章的时间，来讲讲在平时工作中或者面试中比较常见的「排序算法」。

排序算法有很多，而我们只总结和处理我们平时接触到，并用到的，也算是一个针对排序算法的「初级」的汇总和总结。(大神勿喷)

「时间不早了，干点正事哇」。(郭德纲语言包) 针对居中我们有一个「打油诗」

  • 排序算法种类多，常规算法要记牢
  • 「交换排序」找「主元」(pivot)，Bubble/Quick齐上阵
    • Bubble双层循环O(n²)，主元藏于内层循环arr[j]
    • Quick「分治递归」 O(nlogn),partition「中值」效率高
  • 「插入排序」找「哨兵」(sential),Insertion/Shell双胞弟，
    • Insertion区间分「两段」 外层未排i∈ [1,len) 内层已排j ∈ [0,i-1], sential初始为arr[1]
    • Shell while(增量>=1), 内核照抄Insertion 只将i=1/j=i-1改为i=t/j=i-t
  • 「选择排序」找「极值的序号」(minIndex),Selection/Heap一路数
    • Selection区间分「两段」 外层已排i∈ [0,len-1) 内层未排 j∈ [1,len) minIndex初始为i且为「0」
  • 「归并排序」D&C思想好
    • 找前后区间起始位置 i= lo/j=mid 1
    • 找修改原数组的位置 k = lo
    • 复制原数组 copy
    • 数据移动
    • 找「退出条件」 lo>=hi
    • 找「中值」 mid = lo ((hi-lo)>>1)
    • 递归双区间
    • 「先分后治」
    • 分用「递归」来处理
    • 治阶段

文章概要

  1. 交换排序Swap Sort
    • 冒泡排序Bubble Sort
    • 快排序Quick Sort
  2. 插入排序Insertion Sort
    • 插入排序Insertion Sort
    • 希尔排序Shell Sort
  3. 选择排序Selection Sort
  4. 归并排序Merge Sort

知识点简讲

复杂度

❝「复杂度」是衡量代码运行效率的重要「度量」因素 ❞

复杂度是一个关于输入数据量 n 的函数,它有两个特点：

  1. 复杂度与具体的「常系数无关」
  2. 多项式级的复杂度相加的时候，「选择高者」作为结果

O(1)也是表示一个特殊复杂度: 其含义为某个任务通过「有限可数」的资源即可完成。

而复杂度又可以分为

  • 「时间复杂度」:与「代码结构」有着非常紧密的关系
  • 「空间复杂度」:与「数据结构」的设计有关

针对「时间复杂度」，有几个经验性的结论：

代码结构

时间复杂度

「顺序结构」的代码

O(1)

「二分查找」/采用分而治之的「二分策略」

O(nlogn)

简单的 for 循环

O(n)

两个「顺序执行」的 for 循环

O(n) O(n)=O(2n)，即 O(n)

两个「嵌套的」 for 循环

O(n²)

针对在平时算法学习和工作中，我们需要有一个意识：「时间昂贵、空间廉价」。所以，如果遇到复杂度比较高的情况，需要对其进行降阶处理。常规步骤如下：

  1. 先暴力解法：在没有任何时间、空间约束下，完成代码任务的开发
  2. 无效操作处理：将代码中的无效计算、无效存储剔除，降低时间或空间复杂度
  3. 「时空转换」：设计合理数据结构，完成时间复杂度向空间复杂度的转移

针对算法复杂度，其实有一个「大O 表示法」，而上面的介绍只是简单的把一些概念给罗列了一下，如果对如何计算和各种复杂度的分类可以参考一些专业的书。

原地排序和稳定性

❝「原地排序」：指在排序过程中「不申请多余的存储空间」，只利用原来存储待排数据的存储空间进行比较和交换的数据排序 ❞

❝「稳定性」：能保证两个相等的数，经过排序之后，其在序列的「前后位置顺序不变」 （A1=A2，排序前A1在A2前面，排序后A1还在A2前面） ❞

两个变量值互换

现在，存在变量a=1/b=2,想要将它们的值「互换」。

一个信手拈来的代码。

代码语言：javascript复制
let a =1,b=2;
let temp;
temp =a; 
a = b; 
b = temp;

「有问题，没有问题，但是不够优雅」。其实，我们可以不「借用」第三个零时变量就可以将两个变量的值，直接替换了。

我们可以利用位运算的「异或运算符」(^),连续对两个数a和b进行「三次异或运算」，a^=b; b^=a; a^=b;，可以互换它们的值。

代码语言：javascript复制
let a =1,b=2;
a ^ =b;
b ^ =a;
a ^ =b;

利用^处理变量互换，倒是省去了，temp变量了，但是针对位运算的操作，让代码看起来很「晦涩难懂」。

我们可以ES6的一些特性做点事。而这次轮到了解构。

代码语言：javascript复制
let a =1,b=2;
[a,b] = [b,a];

就是这么神奇。

util工具函数

为了篇幅能够紧凑，我们将本文中用到的一些比较常规的函数，汇集到这里。

用于数组 数据交换

代码语言：javascript复制
function swap(arr,i,j) {
  return [arr[i],arr[j]]=[arr[j],arr[i]];
}

用于数据对比

代码语言：javascript复制
const Compare = {
 LESS_THAN: -1,
 BIGGER_THAN: 1
}; 

function defaultCompare(a, b) {
 if (a === b) return 0;
 return a < b ? 
 Compare.LESS_THAN : Compare.BIGGER_THAN; 
}

1. 交换排序Swap Sort

❝「交换排序」最主要的特点就是找主元pivot ❞

冒泡排序Bubble Sort

代码语言：javascript复制
function Bubble(arr){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  for(let i=0;i<len-1;i  ){
    // 注意j的范围[0,len-i-1) =>左关右开
    for(let j=0;j<len-i-1;j  ){
      if(arr[j]>arr[j 1]) 
        swap(arr,j,j 1);
    }
  }
  return arr;
}

上面我们只是构建了一个最简单的BubbleSort，其实还有各种优化的空间。

案例分析

假设，我们现在有arr = [5,4,3,2,1]的数组，要求对该数组，进行排序，使其数据「升序排列」。

通过，一个简单的例子，我们再继续分析，上面的的一些关键点。BubbleSort本质上就是一种SwapSort,而交换排序最关键的点，就是需要在每次遍历过程中寻找「主元」(pivot)。而冒泡排序中，外层循环只是控制，需要最多循环的次数，数据对比和交换是在内层循环中处理。

也就是说

❝「冒泡排序」中内层循环arr[j]是「主元」 ❞

优化处理

在上面的例子中，我们只是构建了一个最简单的例子，其实，针对上面的例子，还有很多需要改进的地方。比如，

  • 在比对的时候，只有在「主元」满足交换条件的时候，才进行后续处理。按升序来举例，只有满足arr[j]>arr[j 1]，才进行数据交换。而对于一些，「天生升序」的序列，没必要每个数据都进行条件判断。此时，我们需要在外层循环定义一个变量isSorted(默认值为true)来标识。
  • 通过配置，能满足「升序/降序」排序

直接上代码了。

代码语言：javascript复制
function Bubble(arr,compareFn = defaultCompare){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  for(let i=0;i<len-1;i  ){
    let isSorted = true;
    for(let j=0;j<len-i-1;j  ){
      if(compareFn(arr[j],arr[j 1]=== Compare.BIGGER_THAN)){
        swap(arr,j,j 1);
        isSorted = false;
      } 
    }
    // 如果在经历过一次内层循环，发现没有需要交换的数据
    // 说明，该序列天生有序，直接返回即可
    if(isSorted) break; 
  }
  return arr;
}

复杂度 & 稳定性

既然聊到了算法，有时候，顺带会问，该算法对应的复杂度。我们就不做具体分析了，直接说结论。

BubbleSort

  • 「时间复杂度」 最好为O(n)(天生有序), 平均为O(n²), 最坏为O(n²)(天生反序)
  • 「空间复杂度」为O(1) (不需要额外的空间，就可以完成排序操作)
  • 稳定排序

快排Quick Sort

❝QuickSort 是对BubbleSort的一种改进，采用了「分而治之」的思路 ❞

「快排」也是「交换排序」的一种。

处理Quicksort主要包含以下「3步」

  1. 从数组中取出一个元素，叫做「主元」（pivot）
  2. 重排序数组
    • 使得所有小于pivot的元素在它前面，
    • 所有大于pivot的元素在它后面，
    • 等于pivot的元素放在哪面都行 这样的划分以后，「pivot的位置已经排好」了,这个过程叫做partition操作
  3. 「递归」地应用步骤2到小于pivot的子数组和大于pivot的子数组

而快排的主要难点就是「如何寻找主元位置」。一般有两种算法：

  • Hoare partition scheme:该模式选择数组中的「中间元素作为 pivot」
  • Lomuto partition scheme:该模式选择数组中的「最后一个元素作为 pivot」

通过一些计算，发现Hoare partition 比 Lomuto partition 高效。所以，我们就直接按照Hoare partition模式(挑选数组中间元素作为pivot)进行算法的书写。

因为，涉及到递归，所以，我们用一个helper来「承接」递归的相关代码。

代码语言：javascript复制
const quickSort = arr => helper(arr,0,arr.length-1);

const helper = (arr,lo,hi) => {
  if(lo>=hi) return ; // 递归出口，防止出现死循环
  
  // 针对当前lo/hi的值，找出对应的pivot的位置 
  const pivot = partition(arr,lo,hi);
  // 递归处理，pivot位置之前的数据
  helper(arr,lo,pivot-1);
  // 递归处理，pivot位置之后的数据
  helper(arr,pivot,hi);
}

partition：找出主元的位置。

代码语言：javascript复制
const partition = (arr,lo,hi) => {
  // 利用 >>运算来计算，lo/hi的中间位置
  const pivot = lo   ((hi-lo)>>1);
  
  let i = lo,j =hi;
  
  while(i<=j){
    // 过滤掉，不需要处理的值
    while(arr[i]<arr[pivot]) i  ;
    while(arr[j]>arr[pivot]) j--;
    
    // 找到，前后各自需要掉包的位置，并且将其swap处理。
    if(i<=j) swap(arr,i  ,j--);
  }
  // 这里是关键点
  return i;
}

我们将主要的步骤的注释都标注在代码中了，后面也是这种处理风格。但是，针对一些需要特别注意的点，有会单拎出来。

针对partition中，while中调用swap的地方需要特别指出。swap(arr,i ,j--),在经过一系列比对后，发现在pivot前后i/j位置，是需要「掉包」的数据。然后，过段启动swap进行数据替换，而此时，一个很小的细节，需要注意，在数据替换完成后，需要将对应的「游标」(指针)进行更新处理。也就是i /j--

案例分析

现在有arr=[3,5,1,6,4,7,2]的数组。对其进行快排处理，使数据升序排列。

划分操作的第一次执行

继续对数组进行处理，此时(「7/6」已经被处理完了)，下面展示了有较小值的子数组执行的划分操作。

复杂度 & 稳定性

QuickSort

  • 「时间复杂度」 最好为O(nlogn), 平均为O(nlogn), 最坏为O(n²)
  • 「空间复杂度」为O(logn)
  • 「不稳定」排序

2. 插入排序Insertion Sort

❝「插入排序」最主要的特点就是找哨兵Sentienl ❞

插入排序Insertion Sort

主要的特点就是：找到「已存数据列表」中插入位置，将数据插入对应位置。

具体思路分析，将数组中的数据分为「两个区间」

  • 未排序区间：
    • 「正向」遍历 (从左向右）
    • 外层循环 i∈ [1,len)
  • 已排序区间：
    • 「初始」已排序区间只有一个元素，就是「数组的第一个元素」,
    • 「反向」遍历 （从右向左）
    • 内层循环 j ∈ [0,i-1]

❝「核心思想」是取未排序区间中的元素，在已排序区间中「找到合适的插入位置」将其插入，并保证已排序区间数据一直有序 ❞

代码语言：javascript复制
function insertionSort(arr){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  let i,j,sential;
  
  // 外层循环：处理未排数据
  for(i=1;i<len;i  ){
    sential = arr[i]; //初始化哨兵
    
    // 内层循环: 在已排数据中，找到合适的位置
    for(j=i-1;j>=0&&arr[j]>sential;j--){
      arr[j 1] = arr[j]; // 数据移动
    }
    arr[j 1] = sential;
  }
  return arr;
}

上面的代码很简单，但是有些比较重要的点，需要重点提醒一下:

  • 外层循环: 从未排数据中取最「左侧」的节点,作为哨兵(sential)
  • 内层循环: 当arr[j]>sential时，需要将已排区间的值，整体「后移」(arr[j 1]=arr[j])
  • 在退出内层循环后，最终的位置被确定，同时，j--的处理，也让最终位置向前偏移,此时j的值，位于sential插入位置的「前一位」 so, arr[j 1]= sential

案例分析

现在有arr=[3,4,2,1]的数组。对其进行快排处理，使数据升序排列。

复杂度 & 稳定性

InsertionSort

  • 「时间复杂度」 最好为O(n), 平均为O(n²), 最坏为O(n²)
  • 「空间复杂度」为O(1)
  • 「稳定」排序

希尔排序Shell Sort

「希尔排序」，也称「递减增量排序算法」，是插入排序的一种更高效的改进版本。该算法实质上是一种「分组插入」方法。

希尔排序的基本思想是:

  1. 先将整个待排序的记录序列分割成为「若干子序列」，然后对其进行「插入排序」
  2. 待整个序列中的记录「基本有序」时，再对「全体记录」进行「插入排序」

算法步骤：

  1. 选择一个「增量序列」 t1，t2，……，tk，其中 ti > tj, tk = 1；
  2. 按增量序列个数 k，对序列进行 「k 趟」排序
  3. 「每趟」排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的「子序列」，分别对各子表进行直接插入排序

针对于 ShellSort最关键的是「增量」的选取标准。有很多标准，对应其复杂度也不尽相同。比较出名的增量公式如下。

  • Hibbard增量 : 通项公式 2^k-1，即1，3，7，15......
  • Sedgewick增量: 通项公式 4^k - 3*2^k 1,即1, 5, 19, 41, 109.....

这篇文章只是为了，罗列常规的排序算法，而不是针对某一个算法进行详细分析。所以，我们选取一种比较通俗易懂的方式来讲解: 「希尔增量-逐步折半的增量方法」

希尔增量-逐步折半的增量方法

代码语言：javascript复制
function ShellSort(arr){
  let len = arr.length;
  if(len<2) return arr; // 边界值处理
  
  //确定希尔增量的初始值（假设为序列长度的一半）
  let t = len>>1;
  
  let i,j,sential;
  
  while(t>=1){// 当增量大于等于1时，执行排序
  
    // 把距离为 t的元素编为一个组，扫描所有组
    // 外循环： 处理未排序数据
    for(i=t;i<len;i  ){ 
      sential = arr[j]; //初始化哨兵
      
      //内层循环: 在已排数据中，找到合适的位置
      for(j=i-t;j>=0&&arr[j]>sential;j=j-t){
        arr[j 1] = arr[j];  // 数据移动
      }
      arr[j 1] = sential;
    }
    
    t = t>>1; //采用折半的方式，减小增量
  }
  return arr;
}

没有对比，就不会发现好玩的东西。很明显，ShellSort核心处理逻辑就是InsertionSort。

<<< 左右滑动见更多 >>>

❝「InsertionSort，认为是 ShellSort增量t =1 处理」 ❞

案例分析

现在有arr=[5,8,6,3,9,2,1,7]的数组。对其进行shell排序处理，使数据升序排列。

复杂度 & 稳定性

ShellSort

  • 「时间复杂度」 最好为O(nlog(n)), 平均为O(n(log(n))²), 最坏为O(n(log(n))²)
  • 「空间复杂度」为O(1)
  • 「非稳定」排序

选择排序Selection Sort

❝「选择排序」最主要的特点就是找极值的序号(minIndex/largestIndex) ❞

实现思路有点类似「插入排序」,将数组中的数据分为「两个区间」

  • 已排序区间：
    • 「初始」已排序区间只有一个元素，就是「数组的第一个元素」即 minIndex=i=0
    • 「正向」遍历 （从左向右）
    • 外层循环 i∈ [0,len-1)
  • 未排序区间：
    • 「正向」遍历 （从左向右）
    • 内层循环 j ∈ [i 1,len)

❝每次会从「未排序区间」中找到「最小的元素」，将其放到「已排序区间」的「末尾」 ❞

代码语言：javascript复制
function selectionSort(arr){
  let len = arr.length;
  if(len<2) return arr; // 处理边界值
  
  let i,j,minIndex;
  // 外层循环: 控制迭代轮次
  for(i=0;i<len-1;i  ){
    minIndex = i;
    // 内层循环：从内层循环中找到最小值的位置
    for(j=i 1;j<len;j  ){
      // 在未排区域寻找最小的数，并记录其位置j
      if(arr[j]<arr[minIndex]) minIndex = j;
    }
    // 内层循环完毕，最小值确定，和已排区间最后一位交互位置
    swap(arr,i,minIndex);
  }
  return arr;
}

案例分析

现在有arr=[5,4,3,2,1]的数组。对其进行「选择排序」处理，使数据升序排列。

复杂度 & 稳定性

SelectionSort

  • 「时间复杂度」 最好为O(n²), 平均为O(n²), 最坏为O(n²)
  • 「空间复杂度」为O(1)
  • 「非稳定」排序

其实，针对利用选择排序的思路实现的排序算法，还有一个堆排序(HeapSort),但是由于篇幅和涉及到的点，有点多，所以以后可以单独出一个关于HeapSort相关的文章。在React -Fiber中用到的调度算中，涉及到「优先队列」(PriorityQueue)其实就可以用二叉堆实现。

4. 归并排序Merge Sort

归并排序是一种「分而治之算法」。其思想是将原始数组切分成较小的数组，直到每个小数组「只有一个位置」，接着将小数组「归并」成较大的数组，直到最后只有一个排序完毕的大数组。

由于是分治法，归并排序也是「递归」的。所以，需要一个helper函数，这点和「快排」很像。

分而治之

该算法采用经典的分治（divide-and-conquer D&C）策略

「分阶段」(divide): 就是「递归拆分」子序列的过程。递归深度为

log_2 n

。

「治阶段」(conquer):将两个已经有序的子序列「合并」成一个有序序列。

代码语言：javascript复制
const mergeSort =(arr) => helper(arr,0,arr.length-1);

function helper(arr,lo,hi)=>{
  if(lo>=hi) return;
  // 从中间将数组分成两个部分
  const mid = lo   ((hi - lo)>>1);
  
  // 分阶段：分别递归地将左右两半排好序
  helper(arr,lo,mid);
  helper(arr,mid  1,hi);
  // 治阶段：将排好序的左右两半合并  
  merge(arr,lo,mid,hi);
}
代码语言：javascript复制
function merge(arr,lo,mid,hi){
  //  i 指针表示左半边的起始位置
  let i = lo;
  //  j 表示右半边的起始位置
  let j = mid   1;
  // k 指针表示从什么位置开始修改原来的数组
  let k = lo;
  
  // 复制一份原来的数组
  const copy = arr.slice();
  
  while(i<=mid && j<=hi){
    if(copy[i]<copy[j]){
      arr[k  ] = copy[i  ];
    }else{
      arr[k  ] = copy[j  ];
    }
  }
  
  while(i<=mid) arr[k  ] = copy[i  ];
  while(j<=hi)  arr[k  ] = copy[j  ];
}

while语句一共出现四种情况：

  1. 左边的数「小于」右边的数，将「左边」的数拷贝到合适的位置，i 指针往前移动一位
  2. 右边的数「小于」左边的数，将「右边」的数拷贝到合适的位置，j 指针往前移动一位
  3. 左半边的数都处理完毕，只剩下右半边的数，只需要将右半边的数「逐个拷贝」过去
  4. 右半边的数都处理完毕，只剩下左半边的数，只需要将左半边的数「逐个拷贝」过去

然后，我们看到了，copy 用于数据比较，arr 用于数据迁移。

k 指针表示从什么「位置」开始「修改原来的数组」。

案例分析

现在有arr=[8,4,5,7,1,3,6,2]的数组。对其进行「选择排序」处理，使数据升序排列。

复杂度 & 稳定性

MergeSort

  • 「时间复杂度」 最好为O(nlog(n)), 平均为O(nlog(n)), 最坏为O(nlog(n))
  • 「空间复杂度」为O(n) （用到copy数组）
  • 「稳定」排序

前后呼应

防止，经过长时间的细节处理，文章刚开始的打油诗估计忘了。然后，再来一遍。

  • 排序算法种类多，常规算法要记牢
  • 「交换排序」找「主元」(pivot)，Bubble/Quick齐上阵
    • Bubble双层循环O(n²)，主元藏于内层循环arr[j]
    • Quick「分治递归」 O(nlogn),partition「中值」效率高
  • 「插入排序」找「哨兵」(sential),Insertion/Shell双胞弟，
    • Insertion区间分「两段」 外层未排i∈ [1,len) 内层已排j ∈ [0,i-1], sential初始为arr[1]
    • Shell while(增量>=1), 内核照抄Insertion 只将i=1/j=i-1改为i=t/j=i-t
  • 「选择排序」找「极值的序号」(minIndex),Selection/Heap一路数
    • Selection区间分「两段」 外层已排i∈ [0,len-1) 内层未排 j∈ [1,len) minIndex初始为i且为「0」
  • 「归并排序」D&C思想好
    • 「先分后治」
    • 分用「递归」来处理 找「退出条件」 lo>=hi 找「中值」 mid = lo ((hi-lo)>>1) 递归双区间
    • 治阶段 找前后区间起始位置 i= lo/j=mid 1 找修改原数组的位置 k = lo 复制原数组 copy 数据移动
shell 编程算法

0 人点赞