发布于 

排序算法备忘录（三）

快速排序

总算到了速度比较快同时也较之前更复杂的算法了。这里的思路和代码参考了菜鸟教程 1 和编程网 2 的文章。

快速排序总的来看是一种分治思想。以从小到大为例，先确定一个基准数 k，这里选择第一个数字，把比 k 小的放在左边，比 k 大的放在右边，这样整个序列对于这三部分来说是有序的。对于左边和右边，分别重复这项操作，选择基准数，然后分成相对有序的三部分。如此循环，最后整个序列就是有序的。

由于涉及到一项重复操作，可以使用递归实现。具体代码如下：

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
# 算法主体
def quick_sort(lst, l, r):
    if l < r:
        key = lst[l]
        i = l
        j = r
        while i < j:
            while i < j and lst[j] > key: # A
                j -= 1
            if i < j:                     # B
                lst[i] = lst[j]
                i += 1
            while i < j and lst[i] < key: # C
                i += 1
            if i < j:                     # D
                lst[j] = lst[i]
                j -= 1
        lst[i] = key                      # E
        quick_sort(lst, l, i-1)           # F
        quick_sort(lst, i+1, r)           # G

# 使用 random 中的 shuffle 生成一个乱序的数字序列
import random
n = 1000
lst = [i for i in range(1, n + 1)]
random.shuffle(lst)

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

这里，每次循环执行四个步骤，步骤 A 用来寻找比 k 小的数，找到它的下标，步骤 B 把找到的数放在左边，由于原本 lst[i] 处的数字在之前已经被 key 变量保存或者上一次循环中已经被 lst[j] 保存，所以可以用 lst[i] 来保存应该放在左边的数字；步骤 C 同理，用来寻找比 k 大的数，找到它的下标，步骤 D 把找到的数字放在右边。循环结束以后，i = j，进行步骤 E，将 k 放在 lst[i] 位置，完成一次放置。这里，步骤 ABCDE 和每当找到合适的数字时，就把它与 k 的位置进行交换是等价的，这样处理只是减少了 k 的重复赋值。接下来，步骤 FG 则是进行递归操作，将左右两部分分别进行同样的放置处理。

在查询时，在 Python 编程网 3 看到另一种实现方法，利用了 Python 比较便捷的列表操作。具体代码是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort2(lst):
    if len(lst) <= 1:
        return lst
    key = lst[0]
    l, r, k = [], [], []
    for i in lst:
        if i > key:
            r.append(i)
        elif i < key:
            l.append(i)
        else:
            k.append(i)
    return quick_sort2(l) + k + quick_sort2(r)

二者思路是一致的，但是第二种方法步骤比较简洁，不同的是，方法 1 利用下标进行数组的划分，不需要返回值，方法 2 通过创建新的列表进行划分。

接下来比较一下这两种方法的速度差异，这里使用 Numba 对第二种方法进行加速:

横坐标表示数量级，规模从 10310^3 到10810^8，纵坐标表示时间，单位是 s。可以看到第二种方法在速度上优于第一种方法，不过它们在 1 亿规模时运行速度与之前差别很大。另外，实际运行中发现程序有着极大的内存占用，最高到了 9GB。

使用 memory_profiler 对内存占用进行简单测试，在 1,000,000 规模下，使用 quick sort 得到的结果：

实际查看任务管理器：

使用 quick sort 2 得到的结果：

实际查看任务管理器：

可以看到，由于方法 2 在递归运行过程中需要创建新的数组，相当于每次递归就把自己的左右两部分分别复制了一次，只不过内部顺序不一样，大小还是一样的，这就造成了较高的内存占用。观察任务管理器，可以发现，方法 1 的内存占用是恒定的，保持在 129.4MB 基本不变化，而方法 2 的内存占用会不断增加到 163.1MB 左右。

事实上，在 Python 编程网的文章中也提到了方法 2 的内存开销过大，并给出了方法 1 的改进方法。虽然从速度上来看，方法 2 的表现更加出色，但两种方法的速度差距并没有十分显著，这时方法 1 是更好的选择。

许可协议

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

分享文章