AI毛毛的blog

基本排序算法之快速排序的Python实现

上一篇中简单实现了冒泡排序，但是这种基于反复交换的算法，每次只比较相邻的两个数，处理大规模数据时效率相当低下，这时候另一种交换算法 - 快速排序就有用武之地了。
顾名思义，快速排序的效率会高一些，其原理也很简单，是在交换算法中使用“分治法”的思想，大致如下：

  1. 如果待排序list中元素数目为0或1这返回；
  2. 在list中任取一个元素作为枢纽(pivot)；
  3. 改pivot将list分割成两部分，小于等于pivot的元素列表作为small_list，大于pivot的作为greater_list；
  4. 对small_list与greater_list重复上述步骤，递归调用直至无法分割。此时得到最终排序后的order_list。

基于这种原理，很容易用Python3的方法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort1(lists):
    """快速排序的递归实现"""
    less = []
    greater = []
    
    if list_check(lists) is False:
        return lists
    
    pivot = lists.pop()
    for val in lists:
        if val <= pivot:
            less.append(val)
        else:
            greater.append(val)
    
    return quick_sort1(less) + [pivot] + quick_sort1(greater)

随机生成5个数测试一下，结果如下图所示：

quick_1.PNG

可以看出虽然排序结果没有问题，但是递归的过程导致装饰器反复计时，以及先为空的列表也被反复打印提示。

首先解决计时的问题，这是python语法糖引起的，用@time_usage修饰的quick_sort1函数，其实相当于quick_sort1 = time_usage(quick_sorted1)，于是递归的时候每次都要在它的作用域内执行时间函数，所以这里就不用语法糖实现它，而改成time_usage(quick_sort1)(RAND_LIST)直接调用就可以了。

另一方面，由于这个实现开辟了新的空间，导致递归中不停的出现空列表，所以会打印出一堆提示来，所以将它改成“就地”排序的操作，即在被分割的列表里直接交换元素，而不把它们存在新的列表里，改进后代码如下：

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
31
32
33
34
35
36
37
38
39
40
41
def quick_sort2(lists):
    """不需要额外开辟空间的快速排序"""
    if list_check(lists) is False:
        return lists
    quicksort_helper(lists, 0, len(lists)-1)
    
    
def quicksort_helper(lists, first, last):
    """另一种递归实现"""
    if list_check(lists) is False:
        return lists
    
    if first < last:
        splitpoint = partition(lists, first, last)
        quicksort_helper(lists, first, splitpoint - 1)
        quicksort_helper(lists, splitpoint + 1, last)
    
    
def partition(lists, first, last):
    """按枢纽点分割列表并返回分割点"""
    pivotvalue = lists[last]
    
    leftmark = first
    rightmark = last - 1
    
    flags = False
    while not flags:
        while leftmark <= rightmark and lists[leftmark] <= pivotvalue:
            leftmark += 1
    
        while lists[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark -= 1
    
        if rightmark < leftmark:
            flags = True
        else:
            lists[leftmark], lists[rightmark] = lists[rightmark], lists[leftmark]
    
    pivotvalue, lists[leftmark] = lists[leftmark], pivotvalue
    
    return leftmark

这样直接在原列表里操作，当然也直接改变了原本的列表元素顺序，下面用它与第二种冒泡排序以及内置sorted函数对比一下效率，使用990个随机数得出的结果如下：

quick_2.PNG

相比第二种冒泡排序，确实快了一些，但是如果我们使用大的数据量，例如当排序10000个数时，发现其会报错，内容为RecursionError: maximum recursion depth exceeded in comparison，因为已经超出了python的默认的递归深度，虽然我们可以用import sys; sys.setrecursionlimit(20000)这种方法将递归深度加大，但是这并不是一种优雅的做法。

在别的一些编程语言里，我们可以使用尾递归来实现快速排序，但是python并没有尾递归优化，所以这里并不是明智的选择；递归中的这种问题大多可以转化成迭代去解决，但是由于需要利用栈手动保存中间变量，实际效率会降低一些，这里就不去实现了。

快速排序中，选取枢纽元其实也会影响算法的执行效率，目前对此算法常用的选取枢纽元的方法为“三数中值分割法”，即选取左端、右端以及中心位置上的三个元素的中值作为枢纽元。

另一方面，相比冒泡排序，快速排序属于不稳定排序，这里引用维基百科对于稳定性的解释：

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。

而快速排序可能会改变原有稳定的键值对顺序，因此是不稳定的。