背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

飞快的递归算法

分区

数组分区的步骤如下：从数组中随机选取一个值作为基准，把所有小于基准的数移动到基准左边，所有大于基准的数移动到基准右边。我们用下面例子中描述的简单算法来实际完成一个分区。

假设数组为：[0,5,2,1,6,3]。

为了统一标准，我们永远选择最右边的值作为基准（严格来说可以选择其他值）。因此这里选择3作为基准。

然后创建两个“指针”：一个指向数组最左边的值，一个指向除基准以外数组最右边的值。

接下来就可以按如下步骤进行分区操作了。稍后我们会用示例数组讲解一遍这些步骤，你现在不用担心看不懂。

(1) 左指针不断右移一格，直到遇到大于或等于基准的数时才停止移动。

(2) 右指针不断左移一格，直到遇到小于或等于基准的数时才停止移动。如果右指针移动到了数组开头，则也需要停止移动。

(3) 在右指针停止移动之后，会出现两种情况。如果左指针遇到（或越过）了右指针，那么就前往第(4)步。否则，就交换左右指针指向的数，并重复前3步。

(4) 最后，交换基准和左指针指向的数。

分区之后，基准左边的值都比它小，右边的值都比它大。这意味着虽然其他值的位置未必正确，但基准本身在数组中的位置已经正确了。

我们用示例数组实践一下以上步骤。

第1步：比较左指针（目前指向0）和基准（值是3）。因为0小于基准，所以下一步中左指针会右移。

第2步：左指针右移。比较左指针（5）和基准。5小于基准吗？因为答案是否定的，所以左指针停止移动。下一步中，右指针会开始移动。

第3步：比较右指针（6）和基准。它指向的值大于基准吗？因为这个值大于基准，所以右指针会继续左移。

第4步：右指针继续左移。比较右指针（1）和基准。因为这个值小于基准，所以右指针停止移动。

第5步：因为两个指针都已经停止移动，所以交换它们指向的数。下一步中，左指针将重新开始移动。

第6步：左指针开始移动。比较左指针（2）和基准。因为这个值小于基准，所以左指针继续移动。

第7步：左指针移动到下一格。此时，两个指针指向了同一个值。比较左指针和基准。因为左指针指向的值大于基准，所以它停止移动。又因为此时左右指针相遇，所以指针移动步骤已经结束了。

第8步：作为分区的最后一步，交换左指针指向的值和基准。

虽然数组尚未完全排序，但我们已经成功完成了分区。换言之，所有小于基准3的数都已经移动到了其左边，而所有大于基准3的数也都移动到了其右边。根据定义，这也意味着3在数组中已经位于正确位置。

下面是Ruby中的SortableArray类，其中的partition!函数和我们介绍的分区方法一致。

class SortableArray
  attr_reader :array
  def initialize(array)
    @array = array
  end
  def partition!(left_pointer, right_pointer)
    # 总是选择最右边的元素作为基准。记录基准的索引，以便后续使用：
    pivot_index = right_pointer
    # 获取基准值：
    pivot = @array[pivot_index]
    # 让右指针指向基准左边的值：
    right_pointer -= 1
    while true
      # 只要左指针指向的值小于基准，就把它右移：
      while @array[left_pointer] < pivot do
        left_pointer += 1
      end
      # 只要右指针指向的值大于基准，就把它左移：
      while @array[right_pointer] > pivot do
        right_pointer -= 1
      end
      # 现在我们已经不再移动左右指针了。
      # 检查左指针是否已经遇到或者越过右指针。如果是，就跳出循环，以便后续在代码中交换基准：
      if left_pointer >= right_pointer
        break
      # 如果左指针还在右指针的左边，那么就交换它们指向的值：
      else
        @array[left_pointer], @array[right_pointer] =
          @array[right_pointer], @array[left_pointer]
        # 把左指针右移一格，准备进行下一轮指针移动：
        left_pointer += 1
      end
    end
    # 作为分区的最后一步，交换左指针指向的值和基准：
    @array[left_pointer], @array[pivot_index] =
      @array[pivot_index], @array[left_pointer]
    # 为了本章后面介绍的快速排序需要，返回左指针：
    return left_pointer
  end
end

快速排序

快速排序算法结合了分区和递归。它的步骤如下。

(1) 对数组执行分区。分区后，基准已经位于正确位置。

(2) 把基准左右的子数组当作新数组，递归执行第(1)步和第(2)步。换言之，我们会分区每个子数组，在子数组的基准两侧得到更小的子数组。随后不断进行分区。

(3) 如果某个子数组没有或者只有一个元素，那么它就是基准情形。我们不对基准情形进行任何操作。

还是以前面见过的数组[0, 5, 2, 1, 6, 3]为例。

首先对整个数组进行分区。因为快速排序的第一步总是这个分区操作，所以上一节就已经完成了快速排序的部分步骤。

分区后的下一步就是对基准左边的子数组进行分区。

现在就可以分区这个子数组了。因为上一节进行到了第8步，所以这里就从第9步开始。

第9步：比较左指针（0）和基准（2）。因为0小于基准，所以右移左指针。

第10步：左指针右移一格，它现在刚好和右指针指向同一个值。比较左指针和基准。因为1小于基准，所以我们继续。

第11步：左指针右移一格，它现在刚好指向基准。此时，因为左指针指向的值等于基准（毕竟它指向的就是基准本身），所以左指针停止移动。这里左指针悄无声息地越过了右指针。不过没关系，算法在这种情况下依然可以正常工作。

第12步：激活右指针。但是因为右指针指向的值（1）小于基准，所以它不用移动。因为左指针已经越过了右指针，所以这次分区的指针移动操作已经结束了。

第13步：接下来交换基准和左指针指向的值。因为左指针就指向基准，所以基准需要和自己交换，不会改变数组。至此，分区已经完成，而基准（2）也移动到了正确位置。

第14步：比较左指针（0）和基准（1）。因为左指针小于基准，所以我们继续。

第15步：左指针右移一格。它现在指向基准。因为左指针指向的值（1）并不小于基准（毕竟它就指向基准），所以它不再移动。

第16步：比较右指针和基准。因为右指针指向的值小于基准，所以不再移动它。又因为左指针已经越过右指针，所以这次分区的指针移动已经完成。

第17步：交换左指针和基准。这次左指针依然指向基准，所以交换不会改变数组。基准现在位于正确位置，分区也结束了。

第18步：比较左指针（6）和基准（5）。因为6大于基准，所以左指针不再移动。

第19步：因为右指针也指向6，所以理论上要把它左移一格。但是，因为6的左边没有格子可以移动，所以右指针也不再移动了。因为左右指针已经相遇，所以这次分区的指针移动已经完成，可以进行最后一步了。

第20步：交换基准和左指针指向的值。基准（5）现在就在正确的位置了。

下面是一个quicksort!方法，可以把它加入前面的SortableArray类中，从而完成整个快速排序算法。

def quicksort!(left_index, right_index)
  # 基准情形：子数组包含0或1个元素
  if right_index - left_index <= 0
    return
  end
  # 为参数范围内的元素分区，获得基准的索引：
  pivot_index = partition!(left_index, right_index)
  # 为基准左边的部分递归调用这个quicksort!方法：
  quicksort!(left_index, pivot_index - 1)
  # 为基准右边的部分递归调用这个quicksort!方法：
  quicksort!(pivot_index + 1, right_index)
end

快速排序的效率

要确定快速排序的效率，首先需要确定一次分区的效率。

分析分区步骤就会发现其中有两类主要步骤。

• 比较：比较指针指向的值和基准。
• 交换：在适当的时候交换左右指针指向的值。

N个数据元素来说，可以认为有1.25N步。因为大O记法忽略常数，所以我们说分区需要O(N)时间。

快速排序一个包含N个元素的数组所需的步数大约是N乘以log N。这正是快速排序的复杂度。它是O(N log N)算法。这是一类全新的复杂度。

总结

快速排序速度飞快，在平均情况下尤其高效。尽管快速排序在最坏情况下（也就是数组完全倒序排列）的表现和插入排序以及选择排序差不多，但它在最常出现的平均情况下要优秀得多。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。