老齐教室

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

作者:Marcus Sanatan

翻译:老齐


介绍

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

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

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

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

快速排序

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

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

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

假设有一个自定义类Person,每个实例都有nameage属性,我们可以按姓名(词典顺序)或按年龄(升序或降序)进行排序。

快速排序算法的原理

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

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

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

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

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

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

一步一步来看看我们计划要做的事情,从而理解以上所说的快速排序算法的执行过程。使用下面显示的数组,我们选择了第一个元素作为主元(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()函数开始:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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()函数:

1
2
3
4
5
6
7
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():

1
2
3
4
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类开始:

1
2
3
4
5
6
7
class Person:
def __init__(self, name, age):
self.name = name
self.age = age

def __str__(self):
return self.name

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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
1
2
3
4
5
6
7
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属性的值进行实际的比较:

1
2
3
4
5
6
7
8
9
10
11
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)

输出是:

1
2
3
4
5
Tim
Dave
Mike
Matthew
Jane

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

优化快速排序算法

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

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

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

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

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

结论

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

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

如果你想了解更多信息,请参阅微信公众号“老齐教室”发布相关排序算法的系列文章。

原文链接:https://stackabuse.com/quicksort-in-python/

关注微信公众号:老齐教室。读深度文章,得精湛技艺,享绚丽人生。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

关注微信公众号,读文章、听课程,提升技能