18. 三种常见算法

[funfish]

前言

先吐槽。
金三银四，最近来我司计划招聘两名前端工程师，一名初级，一名中级，结果前来面试的人络绎不绝，让我也当面试官，结果呢。前来的有一两年工作经验的初级工程师，都是渣渣，不是基础差，就是广度不够，连笔试题目都做不出来，尤其是算法题目，简单的排序都做不出来。给我的感觉，连刚参加工作的我都不如。而后面试的两个中级工程师，面试后感觉也就比我差点，工作经验比我长点，可是这个期望薪水，是不是有点高呀。只是排序算法题大多用的是冒泡法，作为工程师不应该开口闭口都是快排吗。嗯，只是忽然想想自己也只是知道快排的思想，具体怎么实现，就懵逼了，于是才有了这篇博客。

常见的冒泡法

冒泡法的概念，很是基础，基本上C语言入门书籍，都会介绍一遍。算法实现和其名字一样冒泡，(从小到大排)高个子从数组的低序号冒泡到高序号，并结束本轮循环。下轮循环的时候，剔除掉已经排好序的高个子，开始排下个高个子，这样需要写到两个循环。具体实现如下：

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

  return arr;
}

如此计算，自然可以简单的想到啦，当然还有另外一种更傻的方法，就是每次都出一个数字正确排序，再求出下个数的正确排序，如此下来，也是能实现，只是算发并不不好看，先看看具体实现：

const rubbishSort = (arr) => {
  const arrLength = arr.length;
  let sameControl = {};
  let result = [];
  for(let i = 0; i < arrLength; i++) {
    let target = arr[i],
        left = 0,
        same = 0;
    for(let j = 0; j < arrLength; j++) {
      if(arr[j] < target) {
        left++;
      } 
      if(arr[j] === target) {
        same++;
      }
    }
    if(result[left] === undefined) {
      for(let resultIndex = left; resultIndex < left + same; resultIndex++) {
        result[resultIndex] = target;
      }
    }
  }
  return result;
}

上面算法一看还是很麻烦的，为了相同的元素还特地设置了 same 变量，虽然最后也是能实现排序的，只是其计算的步骤却是要比冒泡法高很多的，不仅仅有两个长度为 arrLength 的 for 循环，在最后一个循环里面还要做两次判断。而冒泡法，第二个 for 循环 就要精简很多了。

大O表示法

要如何判断哪种算法更好呢？常用的比较方法是运行时间，通过运行时间来比较，运行时间越少的，自然越优，毕竟计算机是按照一条条指令并行处理的。大O表示法是种特殊的表示法，指出运行速度的快慢。

对于长度为 n 的数组，若用冒泡法需要循环 n 次，每次循环长度从 n 一直下降到 0，可以求得其运行时间为 n²/2，用大O表示法就是 O(n²)，大O法是自然省略前面的常数的。若用第二种算法，逻辑基本差不多，但是其运行时间为 n²，用大O表示法就是 O(n²)。可以看出来后一种的运行时间足足是前者的两倍之长。

虽然如此，但是 O(n²) 这样的时间，你可以忍？如果有1000个数字，那岂不要花 1,000,000 次计算。想想要是计算机这么搞，岂不是累死了。

快速排序算法

面对传统的这些方法，比如上面，每次排好一个位置都需要循环一遍，效率低下，实在麻烦，有没有更好的办法？分而治之就提供了一个很好的思路，就是要将问题从大化小，一个个简单击破，最后合并在一起就好了。在排序的体现上就是将待排序的数组不断的拆分成小数组，最后划分到根本不用排序的数组，再排序合并。

具体怎么做呢？先看看快速排序（Quicksort）的Javascript实现 这里阮老师给出的思想是：

在数据集之中，选择一个元素作为"基准"（pivot）

**通过基准值pivot来实现分而治之的思想，**拆分出小的单元，再仿佛拆分。具体如下：

var quickSort = function(arr) {
　if (arr.length <= 1) { return arr; }
　var pivotIndex = Math.floor(arr.length / 2);
　var pivot = arr.splice(pivotIndex, 1)[0];
　var left = [];
　var right = [];
　for (var i = 0; i < arr.length; i++){
　　if (arr[i] < pivot) {
　　　left.push(arr[i]);
　　} else {
　　　right.push(arr[i]);
  　}
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

这么一看很有分而治之的味道，每次将数组分为两半，分别排序，从而降低迭代次数，实现了优化。在最优的时候，每次都可以将数组分成两半，**于是调用栈为 O(logN)，底数为2，每次调用排序数量为 n，所以时间复杂度为 O(NlogN)，**相比于冒泡的 O(n²)，快了特别多，如当 n = 10000 的时候，相差1000倍。这个过程其实和二分法有点类似了。

上面算法看着好简单，难道传说中的快速排序就是这样的？在上面的例子中可以发现，主要通过 left 和 right 来进行数据存储，也就是说其每次迭代的空间复杂度为 O(n)，而迭代次数为 O(logN)，所以总的空间复杂度为 O(NlogN)。此时，意味着随着待排序对象的加长，其所占用的空间会不断叠加，与之对比冒泡排序的空间复杂度。。。嗯，不就是 O(1)嘛，

空间复杂度的提高也会影响性能。那有没有运行时间又少，空间复杂度又低的呢？下面给出我自己下的方法：

const quickSort = (arr, left, right) => {
  if (arr.length <= 1) { 
    return arr; 
  }
  left = left || 0;
  right = right || arr.length - 1;

  const target = arr[left];
  const leftInit = left;
  const rightInit = right;
  let leftEnd;
  let rightStart;
  let temp;
  left++;

  if(left === right) {
    if(target > arr[right]) {
      temp = arr[left - 1];
      arr[left - 1] = arr[right];
      arr[right] = temp;
    }
    return false;
  }
  while(left < right) {
    while(arr[left] <= target && left < right) {
      left++;
    }
    while(arr[right] > target && left < right) {
      right--;
    }
    if(left < right ) {
      temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
    }
    if(left === right) {
      if(target > arr[left]) {
        arr[leftInit] =  arr[left];
        arr[left] = target;
        leftEnd = left - 1;
      } else if(leftInit !== left -1) {
        arr[leftInit] = arr[left - 1];
        arr[left - 1] = target;
        leftEnd = left - 2;
        rightStart = left;
      } else {
        rightStart = left + 1;
      }
    }
  }
  if(leftEnd !== undefined) {
    qs(arr, leftInit, leftEnd);
  }
  if(rightStart !== undefined) {
    qs(arr, rightStart || right, rightInit)
  }
}

（吐个槽，quickSort 方法，写了一个小时半才写好，一开始以为很简单，结果跑一下，才发现各种bug，实在惭愧，现在有点体谅那些写不出快速排序的面试者了）

具体的思想可以参考这篇 博客。上面的 quickSort 的思想还是很简单的，通过两边不断的推移，将小于 target 的数放在左边，大于 target 的数放在右边。只是可能出现左边的数都小于 target，又或者是左边的数都大于 target，所以需要特别处理，导致复杂度提高了。

这时候看到了 聊聊前端排序的那些事 上面介绍到排序 sort 在 Chrome 中的实现，核心部分还是快速排序，原来 Chrome 里面也是用 JavaScript 来实现 sort 方法的！具体源码，只是没有想到 Chrome 里面居然用了 partition 来跳转 js 代码，太可怕了。

chrome 里面先是对输入数组范围小于10的，采用插入排序，包括迭代过程中也是，否则采用快排。快排中采用三点取值，分别是首尾数值，和中间数值。中间数值的下标会根据数组是否大于 1000 来分情况生成，具体情况请看源码。随后对这三个数值排序，取中间值作为基准。采用的快速方法和上文中的第二种思路相似的，只是用了 for 循环和一个 do while 循环，实现起来也是麻烦不少，但是估计速度会更快，更优秀吧。

快排复杂度

前面有提到快速排序算法的运算时间为 O(NlogN)，这是根据调用栈和每次调用量，来计算的，但是其调用栈却不总是 O(logN)，O(logN) 是建立在每次循环取基准值刚好是该数组的中间值，如果不是中位数值呢？如对数组[1, 2, 3, 4, 5]，这种混乱度低的数组，如果还是用从 0 下标开始的快速排序算法，那其计算下来和普通的冒泡法的运行时间是相似的。

由于这种原因，Chrome 里面的快排用三值分而治之，保证随机性，提高快排的运算效能。快排的最糟糕运行时间为 O(n²)，最佳为 O(NlogN)，当然平均时间为 O(NlogN)，基准值取值随机的情况下， O(n²) 是低概率事件。

归并排序

在 聊聊前端排序的那些事 中看到Firefox采用归并排序，具体缘由文中后面后面也是介绍了一下历史，但是归并排序是什么呢？思路如下图所示

算法也挺简单的，如下：

const mergeSort = (arr) => { 
  const len = arr.length;
  if(len < 2) {
    return arr;
  }
  const middle = Math.floor(len / 2),
      left = arr.slice(0, middle),
      right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

const merge = (left, right) => {
  let result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

上面代码计算参考 这篇博客。

归并也是采用分而治之的思路，和二分法的思路有些接近，就像上图一样，把数组整体分割成最小单元，两个元素或则一个元素。先从小数组中排序，再和相邻的数组间排序，一级一级往上走。可以知道这种方式下，调用栈肯定是 O(logN)，而每次调用运算为 N，所以其运算时间为 O(NlogN)。其运行时间比快排还要稳定，是稳定排序，只是问题在于 result 数组，归并运算的问题在于其空间复杂度为 O(NlogN)，和阮老师里面提到的快速算法空间复杂度是一致的，其实由于反复递归，每次递归的代码执行栈是很高的，相对于上文自己写的快速排序还是有很大差别的。

其他排序

其他排序还有一些很经典的：

1. 插入排序。插排序如同打扑克牌，插入牌一样。从第二个元素开始，每个数都回溯其应该排序位置，和冒泡法的套路有点像。
2. 选择排序；
3. 堆排序；
   当然还有很多，只是怕全都看完容易忘记，还是记住三个常见有用的算法吧。

关于排序，还有个有趣的地方，数组的完全随机排列，洗牌算法和排序算法之间的矛盾问题，算是一个扩展吧。

ps: 为何网上查找的快速排序算法大多不是快速排序，或者是错误的，这如何是好。。。。。。

参考

1. 快速排序（Quicksort）的Javascript实现
2. 聊聊前端排序的那些事
3. 十大经典排序算法