详解 Python 算法：快速排序

快速排序是一种流行的排序算法，经常与归并排序一起使用。快速排序是一个高效的排序算法，平均复杂度为 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)

输出：

[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)

输出是：

Tim
Dave
Mike
Matthew
Jane

通过这种方式实现算法，只要提供适当的比较函数，它就可以用于我们选择的任何自定义对象。

优化快速排序算法

考虑到快速排序独立地对给定数组的“一半”进行排序，那么它就非常便于实现并行计算。我们可以用一个单独的线程对数组的每个“一半”进行排序，理想情况下，可以将排序所需的时间减半。

但是，如果我们在选择主元时特别不走运，快速排序法可能会递归太深，此时即使用并行计算，其效率也不如归并排序。

对小数组进行排序时，建议使用非递归算法。即使是像插入排序这样的简单操作，在小数组上也比快速排序更有效。因此，理想情况下，我们可以检查排序对象是否只有少量元素（大多数建议是 10 个或更少），如果是这样，就用插入排序代替。

快速排序的一个流行变体是多主元快速排序，它使用 n-1 个主元将原始数组分解为 n 个较小的数组。然而，大多数情况下只使用两个主元，而不是更多。

有趣的事实：Java 7 的排序实现中使用了双主元快速排序，针对较小数组的则是插入排序。

结论

正如我们前面提到的，快速排序的效率很大程度上取决于主元的选择——它可以成就或突破算法时间（和堆栈空间）的复杂度。在使用自定义对象时，算法的非稳定性也是一个潜在的问题。

然而，尽管如此，快速排序的平均时间复杂度 O(nlogn) 和相对低的内存使用、简单的实现方法，使它成为一种非常有效和流行的算法。

原文链接：https://stackabuse.com/quicksort-in-python/，作者：Marcus Sanatan