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

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

1、蛋糕问题

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

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

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

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

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

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

  1. 找出基线条件,这个条件要尽可能的简单。
  2. 不断的将问题分解(缩小问题的规模),直至符合基线条件。

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

我们可以从下一个长方形中不断的取出正方形,直至找出不可在划分的情况。在上图中,当划分成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)
  }
}

在递归中需要两个条件:

  1. 基线条件:用于程序的结束
  2. 递归条件:用于进入下一个递归

似乎和我们上面提到的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为基准值,并将这个数组分为两个单独的部分:

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

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

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

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

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

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

  1. 选择基准值
  2. 将数组分为两个子数组:一个小于基准值,一个大于基准值
  3. 对两个子数组再次从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)。