图解快速排序算法

快速排序是一种排序算法,速度要比选择排序快的多,属于优雅代码的典范。本文在讲解快速排序算法之前,先来介绍它的策略–分而治之(divide and conquer, D & C),这是一种著名的递归式问题解决方法。

分而治之

假设你是农场主,有一小块土地:

图片.png

你要将这块地均匀地分成方块,且分出的方块要尽可能大。显然,下面的分法都不符合要求:

图片.png

如何将一块地均匀地分成方块,并确保分出的方块是最大的呢?使用D&C策略!D&C算法 是递归的。使用D&C解决问题的过程包括两个步骤:

(1)找出基线条件,这种条件必须尽可能简单;

(2)不断将问题分解(或者说缩小规模),直到符合基线条件。

下面就来使用D&C找出前述问题的解决方案。可你能使用的最大方块有多大呢? 首先,找出基线条件。最容易处理的情况是,一条边的长度是另一条边的整数倍:

图片.png

如果一边长25m,另一边长50m,那么可使用的最大方块为25m×25m。换言之,可以将这块地分成两个这样的方块。

现在需要找出递归条件,这正是D&C的用武之地。根据D&C的定义,每次递归调用都必须 缩小问题的规模。如何缩小前述问题的规模呢?我们首先找出这块地可容纳的最大方块。

图片.png

你可以从这块地中划出两个640m×640m的方块,同时余下一小块地。现在是顿悟时刻:何不对余下的那一小块地使用相同的算法呢?

图片.png

最初要划分的土地尺寸为1680m×640m,而现在要划分的土地更小,为640m×400m。适用于这小块地的最大方块,也是适用于整块地的最大方块。换言之,你将均匀划分1680m×640m土地的问题,简化成了均匀划分640m×400m土地的问题!

欧几里得算法

前面说“适用于这小块地的最大方块,也是适用于整块地的最大方块”,如果你觉得这一点不好理解,也不用担心。这确实不好理解,但遗憾的是,要证明这一点,需要的篇幅有点长,在本文中无法这样做,因此你只能选择相信这种说法是正确的。如果你想搞明白其中的原因,可参阅欧几里得算法。可汗学院很清楚地阐述了这种算法,网址为https://www.khanacademy.org/computing/computer-science/ryptography/modarithmetic/a/the-euclidean-algorithm。

下面再次使用同样的算法。对于640m×400m的土地,可从中划出的最大方块为400m×400m。这将余下一块更小的土地,其尺寸为400m×240m。

图片.png

你可从这块土地中划出最大的方块,余下一块更小的土地,其尺寸为240m×160m。

图片.png

接下来,从这块土地中划出最大的方块,余下一块更小的土地:
图片.png

余下的这块土地满足基线条件,因为160是80的整数倍。将这块土地分成两个方块后,将不会余下任何土地!

图片.png

因此,对于最初的那片土地,适用的最大方块为80m×80m:

图片.png

这里重申一下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]));

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

第一步:找出基线条件。最简单的数组什么样呢?请想想这个问题,再接着往下读。如果数组不包含任何元素或只包含一个元素,计算总和将非常容易。

图片.png

因此这就是基线条件。

第二步:每次递归调用都必须离空数组更近一步。如何缩小问题的规模呢?下面是一种办法。

图片.png

这与下面的版本等效:

图片.png

这两个版本的结果都为12,但在第二个版本中,给函数sum传递的数组更短。换言之,这缩小了问题的规模!

函数sum的工作原理类似于下面这样:

图片.png

这个函数的运行过程如下:

图片.png

别忘了,递归记录了状态:

图片.png

函数式编程

你可能想,既然使用循环可轻松地完成任务,为何还要使用递归方式呢?看看函数式编程 你就明白了!诸如Haskell等函数式编程语言没有循环,因此你只能使用递归来编写这样的函数。 如果你对递归有深入的认识,函数式编程语言学习起来将更容易。例如,使用Haskell时,你可 能这样编写函数sum。

图片.png

注意,这就像是你有函数的两个定义。符合基线条件时运行第一个定义,符合递归条件时 运行第二个定义。也可以使用Haskell语言中的if语句来编写这个函数。

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

但前一个版本更容易理解。Haskell大量使用了递归,因此它提供了各种方便实现递归的语 法。如果你喜欢递归或想学习一门新语言,可以研究一下Haskell。

快速排序

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

下面来使用快速排序对数组进行排序。对排序算法来说,最简单的数 组什么样呢?就是根本不需要排序的数组:

图片.png

因此,基线条件为数组为空或只包含一个元素。在这种情况下,只需原样返回数组——根本就不用排序:

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

我们来看更长的数组,对包含两个元素的数组进行排序也很容易:

图片.png

包含三个元素的数组呢?

图片.png

别忘了,你要使用D&C,因此需要将数组分解,直到满足基线条件。下面介绍快速排序的工作原理。首先,从数组中选择一个元素,这个元素被称为基准值(pivot)。

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

接下来,找出比基准值小的元素以及比基准值大的元素。

图片.png

这被称为分区(partitioning)。现在你有:

1)一个由所有小于基准值的数字组成的子数组;

2)基准值;

3)一个由所有大于基准值的数组组成的子数组。

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

图片.png

如果子数组是有序的,就可以像下面这样合并得到一个有序的数组:左边的数组+基准值+右边的数组。在这里,就是[10,15]+[33]+[],结果为有序数组[10,15,33]。
如何对子数组进行排序呢?对于包含两个元素的数组(左边的子数组)以及空数组(右边的子数组),快速排序知道如何将它们排序,因此只要对这两个子数组进行快速排序,再合并结果,就能得到一个有序数组!

图片.png

不管将哪个元素用作基准值,这都管用。假设你将15用作基准值:

图片.png

这个子数组都只有一个元素,而你知道如何对这些数组进行排序。现在你就知道如何对包含三个元素的数组进行排序了,步骤如下:

(1)选择基准值。

(2)将数组分成两个子数组:小于基准值的元素和大于基准值的元素。

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

包含四个元素的数组呢?

图片.png

假设你也将33用作基准值:

图片.png

左边的子数组包含三个元素,而你知道如何对包含三个元素的数组进行排序:对其递归地调用快速排序。

图片.png

因此你能够对包含四个元素的数组进行排序。如果能够对包含四个元素的数组进行排序,就能对包含五个元素的数组进行排序。为什么呢?假设有下面这样一个包含五个元素的数组。

图片.png

根据选择的基准值,对这个数组进行分区的各种可能方式如下:

图片.png

注意,这些子数组包含的元素数都在0~4内,而你已经知道如何使用快速排序对包含0~4个元素的数组进行排序!因此,不管如何选择基准值,你都可对划分得到的两个子数组递归地进行快速排序。

例如,假设你将3用作基准值,可对得到的子数组进行快速排序。

图片.png

将子数组排序后,将它们合并,得到一个有序数组。即便你将5用作基准值,这也可行。

图片.png

将任何元素用作基准值都可行,因此你能够对包含五个元素的数组进行排序。同理,你能够对包含六个元素的数组进行排序,以此类推。

归纳证明

刚才你大致见识了归纳证明!归纳证明是一种证明算法行之有效的方式,它分两步:基线条件和归纳条件。是不是有点似曾相识的感觉?例如,假设我要证明我能爬到梯子的最上面。递归条件是这样的:如果我站在一个横档上,就能将脚放到下一个横档上。换言之,如果我站在第二个横档上,就能爬到第三个横档。这就是归纳条件。而基线条件是这样的,即我已经站在第一个横档上。因此,通过每次爬一个横档,我就能爬到梯子最顶端。

对于快速排序,可使用类似的推理。在基线条件中,我证明这种算法对空数组或包含一个元素的数组管用。在归纳条件中,我证明如果快速排序对包含一个元素的数组管用,对包含两个元素的数组也将管用;如果它对包含两个元素的数组管用,对包含三个元素的数组也将管用,以此类推。因此,我可以说,快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明,但它很有趣,并与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]));