前端面试（JavaScript 排序算法）

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢？时间、空间复杂度分析。

时间复杂度
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

1、只关注循环执行次数最多的一段代码
我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度。

function increment(n){
  let sum = 0;
  for(let i=0;i<n;i++){
    sum += i;
  }
  return sum;
}
复制代码

其中第 2 行代码都是常量级的执行时间，与 n 的大小无关，所以对于复杂度并没有影响。循环执行次数最多的是第 4行代码，所以这块代码要重点分析。这行代码被执行了 n 次，所以总的时间复杂度就是 O(n)。

2、加法法则：总复杂度等于量级最大的那段代码的复杂度

function fn(n){
  let n = 0;
  let k = 0;
  
  for(let i=0;i<n;i++){
    n += i;
  }
  
  for(let i=0;i<n;i++){
    for(let j=0;j<n;j++){
      k += i*j;
    }
  }
}
复制代码

综合这段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就为 O(n2)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。

3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

function fn(n){
  let res = 0;
  
  for(let i=0;i<n;i++){
    res += add(i);
  }
  
  return res;
}

function add(n){
  let sum = 0;
  for(let j=0;j<n;j++){
    sum += j;
  }
  return sum;
}
复制代码

我们看函数fn的复杂度，显而易见就是双层循环嵌套。相当于嵌套内外代码复杂度的乘积 O(n) * O(n) = O(n2)

时间复杂度按照从小到大的顺序排列
常数时间 O(1)
对数时间 O(logn)
线性时间 O(nlogn)
二次方 O(n^2)
三次方 O(n^3)
指数时间 O(2^n)
常数阶O(1)

function increment(num){
  return ++num;
}
复制代码

假设运行 increment(1) 函数，执行时间等于X。如果再用不同的参数（例如2）运行一次increment函数，执行时间依然是X。和参数无关，increment函数的性能都一样。因此，我们说上述函数的复杂度是O(1)（常数）。

线性阶O(n)

function sequentialSearch(array, item){ 
  for (var i=0; i<array.length; i++){
    if (item === array[i]){ //{1} 
      return i;
    }
  }
  return -1;
}
复制代码

如果将含10个元素的数组（[1, ...,10]）传递给该函数，假如搜索1这个元素，那么，第一次判断时就能找到想要搜索的元素。在这里我们假设每执行一次行{1} ，开销是1。

现在，假如要搜索元素11。行{1}会执行10次（遍历数组中所有的值，并且找不到要搜索的元素，因而结果返回 -1）。如果行{1}的开销是1，那么它执行10次的开销就是10，10倍于第一种假设

现在，假如该数组有1000个元素（[1, ..., 1000]）。搜索1001的结果是行{1}执行了1000次（然后返回-1）

sequentialSearch 函数执行的总开销取决于数组元素的个数（数组大小），而且也和搜索的值有关。如果是查找数组中存在的值，行{1}会执行几次呢？如果查找的是数组中不存在的值，那么行{1}就会执行和数组大小一样多次，这就是通常所说的最坏情况

最坏情况下，如果数组大小是10，开销就是10；如果数组大小是1000，开销就是1000。可以得出 sequentialSearch 函数的时间复杂度是O(n)，n是（输入）数组的大小

平方阶O(n²)

function swap(arr, i, j){
  [arr[i],arr[j]] = [arr[j],arr[i]]
}
function bubbleSort(array){
 var length = array.length;
 for (var i=0; i<length; i++){ //{1}
  for (var j=0; j<length-1; j++ ){ //{2}
    if (array[j] > array[j+1]){
      swap(array, j, j+1);
    }
  }
 }
}
复制代码

bubbleSort 可以对一个数字数组进行排序运算

如果用大小为10的数组执行 bubbleSort ，开销是_{100。如果用大小为100的数组执行bubbleSort，开销就是}10000。需要注意，我们每次增加输入的大小，执行都会越来越久

时间复杂度O(n)的代码只有一层循环，而O(n2)的代码有双层嵌套循环。如果算法有三层遍历数组的嵌套循环，它的时间复杂度很可能就是O(n3)

对数阶O(logn)

function fn(arr) {
    const len = arr.length  
    
    for(let i=1;i<len;i=i*2) {
        console.log(arr[i])
    }
}
复制代码

这个算法读取一个一维数组作为入参，然后对其中的元素进行跳跃式的输出。这个跳跃的规则，就是数组下标从1开始，每次会乘以二。

如何计算这个函数的时间复杂度呢？在有循环的地方，我们关心的永远是最内层的循环体。这个算法中，我们关心的就是 console.log(arr[i]) 到底被执行了几次，换句话说，也就是要知道 i<n（ len === n） 这个条件是在 i 递增多少次后才不成立的。

假设 i 在以 i=i*2 的规则递增了 x 次之后， i<n 开始不成立（反过来说也就是 i>=n 成立）。那么此时我们要计算的其实就是这样一个数学方程： 2^x >= n

x 解出来，就是要大于等于以 2 为底数的 n 的对数：

image.png

也就是说，只有当 x 小于 log2n 的时候，循环才是成立的、循环体才能执行。注意涉及到对数的时间复杂度，底数和系数都是要被简化掉的。那么这里的 O(n) 就可以表示为： O(n) = logn

线性对数阶O(nlogn)
将 O(logn) 复杂度循环n遍的复杂度就是 O(nlogn)

function fn(arr) {
    const len = arr.length  
    for(let j=0;j<len;j++){
        i = 1;
        while( i < len ){
            i = i * 2;
        }
    }
}
复制代码

空间复杂度
前面我讲过，时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。和时间复杂度相似，它是内存增长的趋势。

常见的空间复杂度有 O(1)、O(n) 和 O(n^2)

O(1)

function traverse(arr) {
    const len = arr.length
    for(let i=0;i<len;i++) {
        console.log(arr[i])
    }
}
复制代码

在 traverse 中，占用空间的有以下变量：

arr    
len   
i
复制代码

后面尽管咱们做了很多次循环，但是这些都是时间上的开销。循环体在执行时，并没有开辟新的内存空间。因此，整个 traverse 函数对内存的占用量是恒定的，它对应的空间复杂度就是 O(1)。

O(n)

function init(n) {
    let arr = []
    for(let i=0;i<n;i++) {
        arr[i] = i
    }
    return arr
}
复制代码

在这个 init 中，涉及到的占用内存的变量有以下几个：

n 
arr
i
复制代码

注意这里这个 arr，它并不是一个一成不变的数组。arr最终的大小是由输入的 n 的大小决定的，它会随着 n 的增大而增大、呈一个线性关系。因此这个算法的空间复杂度就是 O(n)。

由此我们不难想象，假如需要初始化的是一个规模为 n*n 的数组，那么它的空间复杂度就是 O(n^2) 啦。

最好、最坏情况时间复杂度
我们先看一段代码：

function find(arr,x){
    for(let i=0;i<arr.length;i++){
    if(arr[i] === x){
       return i;
       break;
    }
  }
  return -1;
}

find([2,1,3],1);
复制代码

我们在数组中查找一个数据，并不需要每次都把整个数组都遍历一遍，因为有可能中途找到就可以提前结束循环了。

这段代码的时间复杂度还是 O(n) 吗？因为要查找的变量 x 可能出现在数组的任意位置。如果数组中第一个元素正好是要查找的变量 x，那就不需要继续遍历剩下的 n-1 个数据了，那时间复杂度就是 O(1)。但如果数组中不存在变量 x，那我们就需要把整个数组都遍历一遍，时间复杂度就成了 O(n)。所以，不同的情况下，这段代码的时间复杂度是不一样的。

为了表示代码在不同情况下的不同时间复杂度，我们需要引入三个概念：最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

• 最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。
• 最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。

平均情况时间复杂度

平均时间复杂度分析复杂，还要涉及概率论的知识。实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。很多时候，我们使用一个复杂度就可以满足需求了。只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

其实有一个很简单的办法帮助我们来进行粗暴的判断：

上面最好的情况是 O(1) ，最坏的情况是O(n)，直观判断出现O(1)的情况是特别少的。往往都是>1并且小于n的一个值，但是这个值依然是一个变量，因此我们同样可以认为平均时间复杂度就是O(n)。

大O表示法其实本身就是表示代码执行时间随数据规模增长的变化趋势，因此别太较真，较真的话也可以去数学求导，然后去掉系数和常量。

排序算法

以面试为导向来看，需要大家着重掌握的排序算法，主要是以下5种：

• 基础排序算法

  • 冒泡排序
  • 插入排序
  • 选择排序

• 进阶排序算法

  • 归并排序
  • 快速排序

冒泡排序

思路

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

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

演示

image

编码

基础版：

function bubbleSortBase(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]]; // es6 解构赋值
      }
    }
  }
  return arr;
}
复制代码

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

楼上基本冒泡思路的问题在于，没有区别处理这一部分已经有序的元素，而是把它和未排序的部分做了无差别的处理，进而造成了许多不必要的比较。

为了避免这些冗余的比较动作，我们需要规避掉数组中的后 n 个元素，对应的代码可以这样写：

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

改动点：

len-1-i

时间复杂度
最好时间复杂度 ：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
最坏时间复杂度 ： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
平均时间复杂度 ：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可。
选择排序
思路
选择排序的关键字是“ 最小值 ”：循环遍历数组，每次都找出当前范围内的最小值，把它放在当前范围的头部；然后缩小排序范围，继续重复以上操作，直至数组完全有序为止。

演示

image

编码

function selectSort(arr){
  const len = arr.length; // 缓存数组长度
  let minIndex;

  for(let i=0;i<len - 1;i++){

    minIndex = i; // 最小值的位置，先定位数组的第一个

    for(let j=i;j<len;j++){
      // 若 j 处的数据项比当前最小值还要小，则更新最小值索引为 j
      if(arr[j]<arr[minIndex]){
        minIndex = j;
      }
    }

    // 如果最小值的位置，不是初始化时的位置，就可以进行交换了。
    if(minIndex !== i){
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }

  }

  return arr;
}

console.log(selectSort([3,5,8,1,4]));

复制代码

时间复杂度

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

插入排序

思路

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

演示

image

编码

function insertSort(arr){
  const len = arr.length;

  let target;

  for(let i=0;i<len;i++){
    let index = i;
    target = arr[i];

    while(index>0 && arr[index-1] > target){
      arr[index] = arr[index-1]; // 这个步骤相当于是把前面一个值，移动到后面一位来。
      index--;
    }
    // 表明没有进入while循环，因此没有发生位置交换，就不必交换位置了。
    if(arr[index] !== target){
      arr[index] = target ; // 最后确定好的位置，放入上面保存好的值。
    }

  }

  return arr;
}
复制代码

时间复杂度

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

所谓基础排序算法，普遍符合两个特征：

1. 易于理解，上手迅速
2. 时间效率差

上面的三个算法完美地诠释了这两个特征。

那么在此基础上，排序效率如何提升、排序算法如何与进阶的算法思想相结合？下面我们就来介绍两个常用的高级排序算法。

归并排序

“分治”思想

“分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

利用分治思想解决问题，我们一般分三步走：

• 分解子问题
• 求解每个子问题
• 合并子问题的解，得出大问题的解

思路

归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：

• 分解子问题 ：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
• 求解每个子问题 ：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。
• 合并子问题的解，得出大问题的解 ：当数组被合并至原有的规模时，就得到了一个完全排序的数组

演示

image

编码

• 拆分动作：负责拆分数组到期望的粒度
• 合并动作：排序合并数组

const mergeSort = arr => {
  //采用自上而下的递归方法
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  // length >> 1 和 Math.floor(len / 2) 等价
  let middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle); // 拆分为两个子数组
  // 递归拆分
  return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
  const result = [];

  while (left.length && right.length) {
    // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  // left 数组 或者 right 数组剩余的数字插入到 result 数组的后面。
  while (left.length) result.push(left.shift());

  while (right.length) result.push(right.shift());

  return result;
};
复制代码

结合代码分解：

拆分例如：[1,5,3,2]

[1,5] [3,2]
[1] [5] [3] [2]
在合并动作时进行排序：

[1][5] => [1,5]
[2][3] => [2,3]
然后 [1,5] [2,3] 进行合并：

left.length && right.length
while (left.length) result.push(left.shift());

时间复杂度
从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步，又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(n log n)。 最佳情况：T(n) = O(n log n)。 最差情况：T(n) = O(n log n)。 平均情况：T(n) = O(n log n)。

快速排序
快速排序的核心思想，依然是分治法。

思路一
先找到一个基准点（一般指数组的中部），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边；
左右分别用一个空数组去存储比较后的数据；
最后递归执行上述操作，直到数组长度 <= 1。
演示一
[1,5,3,4,2]

第一步：选择中间的元素3作为"基准"。（基准值可以任意选择，但是选择中间的值比较容易理解。）[1,5,3,4,2]
第二步，按照顺序，将每个元素与"基准"进行比较，形成两个子集，一个"小于3"，另一个"大于等于3"。[1,2] 3 [5,4]
第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。[1,2] 3 [5,4]
第四步，递归比较。[1] 2 [] + 3 [] 4 [5]
顺序就出来了。这种思路有一个缺点就是需要再定义两个数组来装比较后的数据。但是实现起来简单易懂。通常在面试中能答出这种思路就可以了。

编码一

const quickSort1 = arr => {
  if (arr.length <= 1) {
    return arr;
  }

  //取基准点
  const midIndex = Math.floor(arr.length / 2);

  //取基准点的值，splice(index,1) 则返回的是含有被删除的元素的数组。
  const valArr = arr.splice(midIndex, 1);

  const midIndexVal = valArr[0];

  const left = []; //存放比基准点小的数组
  const right = []; //存放比基准点大的数组

  //遍历数组，进行判断分配
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < midIndexVal) {
      left.push(arr[i]); //比基准点小的放在左边数组
    } else {
      right.push(arr[i]); //比基准点大的放在右边数组
    }
  }
  
  //递归执行以上操作，对左右两个数组进行操作，直到数组长度为 <= 1
  return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
复制代码

思路二
思路二较思路一主要区别在于，并不会把真的数组分割开来再合并到一个新数组中去，而是直接在原有的数组内部进行排序，节省内存空间。

通常我们能想到的办法就是使用双指针来代替思路一中的两个空数组。

演示二
[5,4,3,1,2]

left 左指针初始值为0，right 右指针初始值为arr.length - 1，第一个基准点是值为3 [5,4,3,1,2]
以3为基准，左指针开始从下标0走起，走到下标为0也就是值为5时，停止下来
右指针，从下标4开始走起，第一个值是2比3小，停止下来。
此时 left = 0，right = 4，在数组中，让两个互换位置结果 [2,4,3,1,5]
此时左指针开始向前走，走下标为1，值为4停下来，右指针走到下表为3，值为1停下来
此时 left = 1，right = 3，在数组中，让两个互换位置结果 [2,1,3,4,5]
交换完位置后，左指针向前进一位，右指针也向左进一位，left = 2 ，right = 2
左指针再向前走一位，left = 3 ，右指针再向左走一位，right = 1；
当left > right 时，一轮比较结束，返回左指针指向的位置。
以左指针为基准把数组“划分”成 [2,1,3] [4,5]
[2,1,3] 都会小于等于 第一轮的基准值 3；[4,5]都会大于等于基准值
不断拆分，不断递归，最后就排好序了。
编码二

function quickSort(arr,left = 0,right = arr.length -1){
    // 如果数组只有一项，是不需要进行排序的。
  if(arr.length <=1){
    return arr;
  }
  // 每次递归分区，数组总是不变，变化的是传入的指针位置，这样就巧妙的代替了两个空数组
  const nextPointer = partition(arr,left,right); 
  
  // 当left左指针小于右指针时，递归调用
  if(left < nextPointer-1){
    quickSort(arr, left, nextPointer-1);
  }
  
  // 此时 nextPointer 相当于拆分后数组的右数组的左指针
  if(nextPointer < right){
     quickSort(arr, nextPointer, right);
  }
  
  return arr;
}

function partition(arr,left,right){
    // 获取基准值
  let pivotVal = arr[Math.floor(left + (right-left)/2)];
  
  let leftPoint = left; 
  let rightPoint = right;
  
  while(leftPoint<=rightPoint){
    while(arr[leftPoint] < pivotVal){
        leftPoint ++; // 左指针指向的值 小于 基准值时 向前走一格;
    }
    
   while(arr[rightPoint] > pivotVal){
        rightPoint --; // 右指针指向的值 大于 基准值时 向左走一格;
   }
    
   // 左指针小于等于右指针时，才进行交换位置
   if(leftPoint<=rightPoint){
     // 解构赋值交换数组位置
    [arr[leftPoint], arr[rightPoint]] = [arr[rightPoint], arr[leftPoint]];
     // 每次交换完位置后，指针都移动到下一位
     leftPoint ++;
     rightPoint --;
   }
  }
  
  return leftPoint; 返回左指针的位置，以此为基准去划分数组。
}

复制代码

有想了解更多的小伙伴可以加Q群链接里面看一下，应该对你们能够有所帮助。