图解快速排序算法

快速排序是一种比选择排序快得多的排序算法，是优雅代码的典范。 在讲解快速排序算法之前，本文首先介绍一下它的策略——分而治之（还有，D&C），这是一种著名的递归问题解决方法。

分而治之

假设你是一名农民，拥有一小块土地：

你想将土地均匀地划分为正方形，并且划分的正方形应该尽可能大。 显然，以下划分均不符合要求：

如何将一块土地均匀地划分为正方形，并保证划分出来的正方形是最大的？ 使用D&C策略！ D&C 算法是递归的。 使用 D&C 解决问题的过程包括两个步骤：

(1) 确定基线条件，基线条件必须尽可能简单；

（2）不断分解（或缩小）问题，直到满足基线条件。

让我们用D&C来寻找上述问题的解决方案。 但是您可以使用的最大立方体是多少？ 首先，找出底线条件。 最容易处理的情况是当一侧的长度是另一侧的整数倍时：

如果一侧长 25m，另一侧长 50m，则可使用的最大块为 25m x 25m。 换句话说，土地可以分为两个这样的正方形。

现在我们需要弄清楚递归条件，这就是D&C的用武之地。根据D&C的定义，每次递归调用都必须减小问题的规模。 我们怎样才能减少上述问题的规模呢？ 我们首先找到这块土地可以容纳的最大正方形。

你可以从这块土地上切出两个 640m x 640m 的方块，留下一小块土地。 现在是顿悟的时刻：为什么不对剩下的一小块土地使用相同的算法呢？

原划地面积为1680m×640m，现划地面积缩小为640m×400m。 适合小土地的最大块也是适合整个土地的最大块。 也就是说，你把1680m×640m土地的均分问题简化为640m×400m土地的均分问题！

欧几里得算法

如果您觉得难以理解“适合这一小块地的最大正方形也是适合整个地块的最大正方形”，请不要担心。 这确实很难理解，但不幸的是，证明它会有点长，而且我在本文中无法做到这一点，所以你必须选择相信这个说法是真的。 如果您想了解原因，请参阅欧几里得算法。 可汗学院在 上非常清楚地解释了该算法。

下面再次使用相同的算法。 对于 640m x 400m 的土地，可以从中绘制的最大正方形为 400m x 400m。 这将留下一块较小的土地，尺寸为 400m x 240m。

你可以从这块土地上画出最大的正方形，留下一块较小的土地，其大小为240m x 160m。

接下来，从这块土地上画出最大的正方形，留下一个较小的土地：

剩下的一块土地满足基准条件，因为160是80的整数倍。将这块土地分成两个正方形后，就没有剩余的土地了！

因此，对于原来的一块土地，有效的最大正方形是 80m x 80m：

以下是 D&C 工作原理的回顾：

(1) 确定简单的基线条件；

(2) 确定如何减小问题的规模，使其满足基线条件。

D&C不是一种可以用来解决问题的算法，而是一种解决问题的思维方式。

让我们看另一个例子。 给定一个数字数组，您需要将这些数字相加并返回结果。 使用循环可以轻松完成此类任务：

def sum(arr):
    total=0
for x in arr:
        total+=x
return total
print(sum([1,2,3,4]));

但是如何使用递归函数来完成这种任务呢？

第 1 步：找到基线条件。 最简单的数组是什么？ 请在继续阅读之前思考这个问题。 如果数组不包含元素或仅包含一个元素，则计算总和非常容易。

这就是基准条件。

第二步：每次递归调用都必须向空数组靠近一步。 如何减少问题的规模？ 这是一种方法。

这相当于以下版本：

两个版本的结果都是 12，但在第二个版本中，传递给函数 sum 的数组更短。 换句话说，这减少了问题的规模！

函数 sum 的工作原理如下：

该函数的操作如下：

不要忘记，递归记录状态：

函数式编程

您可能会想，当使用循环可以轻松完成任务时为什么要使用递归？ 看看函数式编程你就明白了！ 、 等函数式编程语言没有循环，因此只能使用递归来编写此类函数。 如果您对递归有深入的了解，函数式编程语言会更容易学习。 例如，在使用时，您可以像这样编写函数 sum

请注意，就像该函数有两个定义一样。 第一个定义在满足基线条件时运行，第二个定义在满足递归条件时运行。 也可以使用语言中的 if 语句来编写此函数。

sum arr = if arr == []
then 0
else (head arr) + (sum (tail arr))

但以前的版本更容易理解。 递归被大量使用，因此它提供了各种方便的语法来实现递归。 如果您喜欢递归或想学习新语言，请查看。

快速排序

快速排序是一种常用的排序算法，它比选择排序快得多。 例如，C语言标准库中的函数qsort就实现了快速排序。 快速排序也使用 D&C。

让我们使用快速排序对数组进行排序。 排序算法最简单的数组是什么？ 是一个根本不需要排序的数组：

因此，基线条件是数组为空或仅包含一个元素。 在这种情况下，只需按原样返回数组 - 根本不排序：

def quicksort(array):
if len(array) < 2:
return array

让我们看看更长的数组。 对具有两个元素的数组进行排序也很容易：

包含三个元素的数组怎么样？

不要忘记，您将使用 D&C，因此您需要分解数组直到满足基线条件。 这是快速排序的工作原理。 首先，从数组中选择一个元素，称为主元。

如何选择合适的基准值将在后面介绍。 我们暂时使用数组的第一个元素作为基值。

接下来，查找小于基值的元素和大于基值的元素。

这称为分区（）。 现在你有：

1）由所有小于基值的数字组成的子数组；

2）基线值；

3) 由所有大于主元值的数组组成的子数组。

这里只进行分区，得到的两个子数组是无序的。 但如果两个数组已排序，则对整个数组进行排序将非常容易。

如果子数组是有序的，则可以将它们合并为有序数组，如下所示：左数组+参考值+右数组。 这里是[10,15]+[33]+[]，结果是一个有序数组[10,15,33]。

如何对子数组进行排序？ 对于包含两个元素的数组（左边的子数组）和一个空数组（右边的子数组），快速排序知道如何对它们进行排序，所以只要快速排序两个子数组并将结果合并，就可以得到一个有序数组！

无论使用哪个元素作为参考值，这都有效。 假设您使用 15 作为基值：

子数组都只有一个元素，并且您知道如何对这些数组进行排序。 现在您知道如何对包含三个元素的数组进行排序，步骤如下：

(1) 选择参考值。

(2) 将数组分为两个子数组：小于参考值的元素和大于参考值的元素。

(3) 对两个子数组进行快速排序。

具有四个元素的数组怎么样？

假设您还使用 33 作为基值：

左侧子数组包含三个元素，并且您知道如何对三个元素的数组进行排序：对其递归调用快速排序。

因此，您可以对包含四个元素的数组进行排序。 如果可以对包含四个元素的数组进行排序，则可以对包含五个元素的数组进行排序。 为什么？ 假设您有以下包含五个元素的数组。

根据所选的基值，对该数组进行分区的各种可能方法如下：

请注意，这些子数组包含 0 到 4 之间的元素，并且您已经知道如何使用快速排序对包含 0 到 4 个元素的数组进行排序！ 因此，无论基值如何选择，都可以对划分得到的两个子数组递归地进行快速排序。

例如，如果使用 3 作为主元值，则可以对结果子数组执行快速排序。

对子数组进行排序后，将它们合并以获得排序后的数组。 即使您使用 5 作为基值，这也有效。

使用任何元素作为主值都可以，因此您可以对五个元素的数组进行排序。 以同样的方式，您可以对具有六个元素的数组进行排序，依此类推。

归纳证明

您刚刚粗略地了解了归纳证明！ 归纳证明是证明算法有效的一种方法，它由两个步骤组成：基线条件和归纳条件。 是不是有一种似曾相识的感觉？ 例如，假设我想证明我可以爬到梯子的顶部。 递归条件是这样的：如果我站在一个梯级上，我可以把脚放在下一个梯级上。 换句话说，如果我站在第二级梯级上，我就可以爬到第三级梯级。 这就是感应条件。 基线条件是我已经处于第一级。 因此，通过一次爬一级，我就到达了梯子的顶部。

对于快速排序，可以使用类似的推理。 在基线条件下，我证明了该算法适用于空数组或包含一个元素的数组。 在归纳条件下，我表明，如果快速排序适用于具有一个元素的数组，那么它将适用于具有两个元素的数组，如果它适用于具有两个元素的数组，那么它也适用于具有三个元素的数组，依此类推。 因此，我可以说快速排序适用于任何长度的数组。 这里没有深入讨论归纳证明，但它们很有趣并且与 D&C 协同工作。

下面是快速排序的代码：

def quicksort(array):
if len(array) < 2:
return array
else:
        pivot = array[0]
        less = [i for i in array[1:] if i<= pivot]
        greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10,5,2,3]));