通俗易懂讲算法：快速排序

2020-02-04

作者：Marcus Sanatan

翻译：老齐

介绍

快速排序是一种流行的排序算法，经常与归并排序一起使用。快速排序是一个高效的排序算法，平均复杂度为O(nlogn)。它受欢迎的部分原因还在于易于实施。

在本文中，我们将先使用整数集合演示快速排序算法，然后会用自定义对象深入探讨这种算法的实现方式。

在分治法、原地排序和非稳定排序中，都有快速排序算法。

在分治法中，对大数组使用递归进行排序之前，使用快速排序算法将数组拆分为更小的数组，直到最后得到一个空数组或只有一个元素的数组。
在原地排序中，快速排序不创建数组的任何副本，它在内存中完成所有的操作。
稳定排序指相同的值在数组中的顺序也是相同的，非稳定的排序算法不能保证这一点，只能说这样的顺序当然有可能出现，但不能保证。这在针对对象排序而不是对基本类型排序时变得很重要。例如，假设有几个自定义的Person类实例具有相同的age，即21岁的Dave和21岁的Mike。如果要对包含Dave和Mike的集合使用快速排序法按年龄排序，则无法保证每次运行算法时Dave都会出现在Mike之前，反之亦然。

快速排序

快速排序算法的执行流程如下：

将集合分成两个（大致）相等的部分，取一个伪随机元素并将其用作主元（注： “主元”，原文中pivot，在多数介绍快速排序算法的中文资料中，并不对齐单独命名，只简单说成是“分割点”，即划分集合的元素，但本文作者使用了pivot这个词来表示“分割点”，译者认为很便于理解和表述，并将其翻译为“主元”）。
小于主元的元素将移动到其左侧，大于主元的元素将移动到其的右侧。
分别对于主元左侧和右侧的元素，重复此上述，直到对整个数组完成排序。

当我们将某个元素描述为比另一个元素“大”或“小”时，并不一定意味着这些元素是整数，我们可以自定义对象，并根据选择的任何属性进行排序。

假设有一个自定义类Person，每个实例都有name和age属性，我们可以按姓名（词典顺序）或按年龄（升序或降序）进行排序。

快速排序算法的原理

对于快速排序算法，很多时候，数组是不能等分的，这是因为整个过程取决于如何选择主元。我们需要选择一个主元，使其比一半的元素大，比另一半的元素小。尽管这个过程看起来很直观，但很难做到。

想一想：如何为数组选择合适的主元？关于这个问题的解决方法，在快速排序算法的发展史上有过好多种。如果随机选择，是行不通的，因为这不能保障主元是合适的，随机选择的代价会非常“昂贵”。此外，还曾经有人提出从中间选择一个元元素，或者选择第一个、或者后半部分中间的，设置用更复杂的递归公式选择，等等。

最直接的最简单的方法是选择第一个（或最后一个）元素作为主元，具有讽刺意味的是，这会导致快速排序法对已经排序（或几乎排序了）的数组执行效果非常糟糕。

但是，大多数人还是用这种方法来实现快速排序算法，因为它很简单，而且这种选择主元的方式是一种非常有效的操作（我们需要重复执行），这也正是我们下面要做的。

既然我们选择了一个主元，接下来该用它做些什么？同样，有几种方法可以处理各个分区。我们要设置三个指针，有一个指向主元，另外两个分别指向“较小”元素和“较大”元素。

然后移动元素，使所有小于主元的元素都在左侧，而所有较大的元素都在右侧。更小或更大的元素不一定会被排序，我们只希望它们位于主元的适当的一侧。然后，用递归方法遍历主元的左侧和右侧。

一步一步来看看我们计划要做的事情，从而理解以上所说的快速排序算法的执行过程。使用下面显示的数组，我们选择了第一个元素作为主元（29），low表示指向较小元素的指针，最右边的high表示指向较大元素的指针。

29是第一主元，low指向99，high指向44

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)

high从右向左移动，直到找到一个小于主元的值

29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (high),44

现在high指向了21，它是一个比主元小的元素，我们想在数组的开头附近找到一个值，使之可以用于与21交换。用一个比主元还小的值交换是没有意义的，所以如果low指向一个更小的元素，我们试着找到一个更大的元素。
将low变量向右移动，直到找到一个大于主元的元素。幸运的是，low已经定位在99，它就比主元大
交换high和low指向的元素：

29 | 21 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,99 (high),44

在我们这样做之后，就将high继续向左移动，将low向右边移动（21和99现在所处的位置是正确的）。
再次，将high向左移动，下一个数字就是小于主元的12。
现在我们通过将low向右移动来找一个大于主元的值，就是41了，它是第一个这样的值

不断重复上述过程，直到low指针和high指针最终在某个元素相遇：

29 | 21,27,12,19,28 (low/high),44,78,87,66,31,76,58,88,83,97,41,99,44

不再使用29作为主元了，所以剩下唯一要做的就是交换主元和high所指元素28，然后我们就完成了这个递归步骤：

28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44

如你所见，我们已经让小于29的所有值现在都在29的左侧，大于29的所有值都在右侧。

然后，算法对28、21、27、12、19（左侧）集合和44、78、87、66、31、76、58、88、83、97、41、99、44（右侧）集合执行相同的操作。

实现

对数组排序

快速排序是一种自然递归算法，将输入数组分成较小的数组，将元素移动到主元的适当一侧，然后重复。

让我们来看看几个递归调用：

当第一次调用算法时，我们考虑所有的元素——从索引0到n-1，其中n是数组中的元素数量。
如果主元最终位于位置k，那么我们将对从0到k-1和从k+1到n-1的元素重复该过程。
在将元素从k+1排到n-1时，当前主元将在某个位置p结束。然后我们将元素从k+1序到p-1，从p+1排序到n-1，依此类推。

也就是说，我们将使用两个函数： partition()和quick_sort()。quick_sort()函数将首先用partition()函数对集合分组，然后在每组上递归调用自己。

下面从partition()函数开始：

def partition(array, start, end):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        # If the current value we're looking at is larger than the pivot
        # it's in the right place (right side of pivot) and we can move left,
        # to the next element.
        # We also need to make sure we haven't surpassed the low pointer, since that
        # indicates we have already moved all the elements to their correct side of the pivot
        while low <= high and array[high] >= pivot:
            high = high - 1

        # Opposite process of the one above
        while low <= high and array[low] <= pivot:
            low = low + 1

        # We either found a value for both high and low that is out of order
        # or low is higher than high, in which case we exit the loop
        if low <= high:
            array[low], array[high] = array[high], array[low]
            # The loop continues
        else:
            # We exit out of the loop
            break

    array[start], array[high] = array[high], array[start]

    return high

最后，让我们实现quick_sort()函数:

def quick_sort(array, start, end):
    if start >= end:
        return

    p = partition(array, start, end)
    quick_sort(array, start, p-1)
    quick_sort(array, p+1, end)

有了这两个函数，就可以对一个简单的数组执行quick_sort():

array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]

quick_sort(array, 0, len(array) - 1)
print(array)

输出：

1	[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]

由于此算法是非稳定的，所以不能保证这两个44的顺序总是这样的，也许会交换 —— 虽然这在整数数组中意义不大。

对自定义对象进行排序

有几种方法可以重写此算法，以便在Python中对自定义对象进行排序。一种非常典型的Python方法是实现给定类的比较运算符，这意味着我们实际上不需要更改算法实现，因为>、=、<=等也可以应用于类对象。

另一个选择是以参数的方式给函数传入一个比较函数，用这个方法来执行对象的实际比较。用这种方式重写算法函数以用于自定义对象是相当简单的。但是请记住，算法并不稳定。

让我们从Person类开始：

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return self.name

这是一个非常基本的类，只有两个属性，name和age。我们希望使用age作为排序键，这将通过为排序算法提供自定义lambda函数来实现。

但首先，让我们看看如何在函数中实现算法。我们没有直接使用<=或>=运算符进行比较，而是在函数中来判断哪个Person实例的年龄更高：

def partition(array, start, end, compare_func):
    pivot = array[start]
    low = start + 1
    high = end

    while True:
        while low <= high and compare_fun(array[high], pivot):
            high = high - 1

        while low <= high and not compare_fun(array[low], pivot):
            low = low + 1

        if low <= high:
            array[low], array[high] = array[high], array[low]
        else:
            break

    array[start], array[high] = array[high], array[start]

    return high

def quick_sort(array, start, end, compare_func):
    if start >= end:
        return

    p = partition(array, start, end, compare_func)
    quick_sort(array, start, p-1, compare_func)
    quick_sort(array, p+1, end, compare_func)

现在，让我们对这些实例对象的集合进行排序。你可以看到，在quick_sort函数的参数中，有lambda函数，它会对age属性的值进行实际的比较:

p1 = Person("Dave", 21)
p2 = Person("Jane", 58)
p3 = Person("Matthew", 43)
p4 = Person("Mike", 21)
p5 = Person("Tim", 10)

array = [p1,p2,p3,p4,p5]

quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age)
for person in array:
    print(person)

输出是: