前端基础算法——快速排序

快速排序算是非常经典与优雅的排序算法之一了，去年前端圈闹得沸沸扬扬的一件事也与它有关。不过阮一峰老师写的快速排序算法我一直没去看过，所以不予置评。

1、蛋糕问题

与二分查找与选择排序不同，快速排序我决定详细的把自己的理解分享出来，在讨论快速排序之前，我们来思考这样一个问题。假设你的朋友过生日，订了一个长64cm宽40cm的蛋糕，现场他问了一个问题：这个长方形至多能切多少个最大的小正方形？

我们把上面那个问题捋一捋：

长方形的蛋糕
切的最多
切出来的蛋糕是最大的正方形

那么我们该怎么做呢？有一句话说的非常好：“如果这个问题无法解决，那就解决提出这个问题的人。”这是一个不错的方案，开玩笑。因为这个问题是可以解决的，这也就引出了一种思想——分治法（divide and conquer, D&C），那么下面，我们就用这种思想来切这一块蛋糕。

我们先把蛋糕放在这里，讨论一种极端理想的情况，如果这个蛋糕的长是64cm宽是32cm，那我们就很好分了，那么最大我们可以切成32cm X 32cm的正方形蛋糕，至多可以切成两块。

当然，这是在一个理想的情况下，事实上我们手上的这块蛋糕要复杂一些。这个时候我们就需要用D&C策略了，使用D&C解决问题大致分为两个步骤：

找出基线条件，这个条件要尽可能的简单。
不断的将问题分解（缩小问题的规模），直至符合基线条件。

那么我们应该怎样将问题分解，直至符合基线条件呢？

我们可以从下一个长方形中不断的取出正方形，直至找出不可在划分的情况。在上图中，当划分成16cm X 8cm时，蛋糕适用的最大正方形是8cm X 8cm，而且无法再进行划分。那么，这个划分蛋糕的问题就解决了，这整块蛋糕如果划分成8cm X 8cm一块的正方形时，将能划分成最多且最大的正方形块。如果想搞清楚这是为什么，可以参阅欧几里得算法。

2、求和问题

在写这篇文章时，我真好看到这样一篇微博：

这相当于给定一个1到100数组以此加下去：

function sum (arr) {
  let total = 0
  for (let i = 0; i < arr.length; i++) {
    total += arr[i]
  }
  return total
}

那么假设我们需要求数组：[1, 2, 3]的和，那我们可以直接调用：sum([1, 2, 3])，但上述代码不符合D&C策略，让我们回顾一下D&C策略的工作原理，首先要找打最简单的基线条件，那么在这里的基线条件就应该是数组为空[]或者只有一个元素[1]，那么sum([1, 2, 3])就等效于1 + sum([2, 3])，这两种情况结果都是6。但第二种情况缩小了问题规模！

如果你清楚递归的条件，那么在这里你很容易想到使用递归来实现第二种版本，虽然使用递归会占用更多内存，且一个不小心就会出错，但我们可以尝试以下：

function sum (arr = []) {
  if (arr.length <= 1) {
    return arr[0] ? arr[0] : 0
  } else {
    return arr.shift() + sum(arr)
  }
}

在递归中需要两个条件：

基线条件：用于程序的结束
递归条件：用于进入下一个递归

似乎和我们上面提到的D&C策略条件有点相似，在上面的递归函数中，我们判断数组中为空或者为1个元数时为基线条件，这个一个及小的范围，试想一下，当我们只要给一个数求和时，是不是为它本身？

那么使用递归去求和[1, 2, 3]就相当于：

sum([1, 2, 3]) => 1 + sum([2, 3]) => 2 + sum([3]) => sum([3]) => 3

这样一步一步缩小了问题的规模。

3、快速排序

终于到了真正的内容了，还记得上面说的最简单情况吗？就是数组为空或是一个元素，因为这样的数组根本不需要排序。因此我们的基线条件也是数组为空或是为一个元素。那么这段程序就很容易开始了：

function quickSort (arr = []) {
  if (arr.length <= 1) {
    return arr
  }
}

我们来看看稍微复杂一点的情况，数组：[1, 2]，对两个元素的数组排序很容易，只要判断第一个是否比第二个元素小即可。

那么包含三个元素的数组呢？[3, 2, 1]，我们怎么将他升序排列呢？

还记得D&C吗，我们现在就需要将数组分解，直到满足基线条件。那么此时我们可以介绍一下快速排序的原理：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

这是百度百科的描述，但有一点上面没说明，就是这两个单独的部分怎么分？随心所欲的分吗？没错，是这样的，但这是基于一个基准值，这个基准值是从数组中选择的一个元素。

比如上述[3, 2, 1]我们怎么做呢？

我选择第一个元素3为基准值，并将这个数组分为两个单独的部分：

小于基准值的数组部分：[2, 1]
大于基准值的数组部分：[]

这样的操作被称为分区（partitioning）,那么现在，我们大致知道了这组数组的三个情况：

一个小于基准值的子数组
基准值
一个大于基准值的子数组

虽然得到了两个子数组，但小于基准值的数组部分依然不是我们想要的升序。但如果假设这个子数组是升序，我们就很好办了，只需要将：小于基准值的子数组 + 基准值 + 大于基准值的子数组，即可得到一个升序的完整排序。

但实际情况并非如此，我们是否可以对子数组进行二次分区呢？答案是肯定的，因为小于基准值的子数组还不符合基线条件。那么把上面的情况用伪代码表示出来就是：
quickSort({[2, 1]) + [3] + quickSort([])
实际用JavaScript表达出来：
quickSort([2, 1]).concat([3], quickSort([]))

那么既然这样我们就很好办了，我们只需要按照下面这三步执行即可：

选择基准值
将数组分为两个子数组：一个小于基准值，一个大于基准值
对两个子数组再次从1开始

那么以此类推，我们用代码写出来是怎样的呢？

function quickSort (arr = []) {
  if (arr.length <= 1) {
    // 基线条件
    return arr
  } else {
    // 递归条件
    
    // 基准值
    let base = arr.shift()
    
    // 小于基准值的子数组
    let less = arr.filter((curr) => { return curr <= base })
    
    // 大于基准值的子数组
    let greater = arr.filter((curr) => { return curr > base })
    
    // 合并数组，并将不符合基准值的子数组再次进行递归分区
    return quickSort(less).concat([base], quickSort(greater))
  }
}

快速排序

快速排序的平均运行时间为O(n log n)，注意这里我用的是平均时间。快速排序最糟糕情况是O(n^2)，最佳情况是：O(n log n)。