介绍

快速排序（ quicksort）是一种经典的排序算法，具有较高的效率和普遍的应用。快速排序的总体思路也是把一个较大的序列，不断细分为较小序列，并递归地调用快速排序对每一小段分别排序。(类似于一分二，二分四，和多线程差不多)

实现代码

def quicksort(arr):
    if len(arr) <= 1:  # 比较每次序列长度是否大于等于1
        return arr
    else:
        pivot = arr[0]  # 设置一个比较基准点
        left = []  # 比较列表_左
        right = []  # 比较列表_右
        for i in range(1, len(arr)):  # 遍历
            if arr[i] < pivot:  # 比较-比基准点小的元素放入列表 left
                left.append(arr[i])
            else:  # 比基准点大的元素放入列表 right
                right.append(arr[i])
        return quicksort(left) + [pivot] + quicksort(right)  # 将left和right两个列表分别递归调用quicksort函数进行排序，并将排序后的列表和基准点组合成一个新的列表

原理

变量 arr 表示待排序的序列，如果序列长度小于等于1，则直接返回该序列；否则，我们选取序列的第一个元素作为比较基准点 pivot，将剩余元素分别放入左右两个列表 left 和 right 中，左边的元素都小于等于基准点，右边的元素都大于基准点。然后，我们递归地对左右两个子序列进行排序，并将排序后的列表和基准点组合成一个新的列表返回。在递归调用过程中，左右子序列也会不断地划分成更小的子序列，直到每个子序列只包含一个元素为止，这样整个序列就变成了有序的。

important

最后，我们来解释一下上面代码中最重要的一行：

return quicksort(left) + [pivot] + quicksort(right)

该行代码表示将 left 和 right 两个列表分别递归调用 quicksort 函数进行排序，并将排序后的列表和基准点 pivot 组合成一个新的列表。具体来说，quicksort(left) 和 quicksort(right) 会递归地对 left 和 right 两个列表进行排序，返回排序后的列表。而 + 运算符则表示将两个列表按顺序合并成一个新的列表，其中 left是基准点左侧的，pivot 表示比较基准点，right是基准点右侧的，把它仨合起来就行了。

应用

将上述代码应用到一个例子中，以更好地理解快速排序算法的具体实现。假设我们要排序的序列为 [4, 6, 1, 3, 8, 2, 9, 7, 5]，则按照上面的代码进行快速排序的过程如下所示：

1. 选取序列的第一个元素 4 作为比较基准点 pivot。
2. 遍历序列，将小于 4 的元素 [1, 3, 2] 放入左边的列表 left 中，将大于 4 的元素 [6, 8, 9, 7, 5] 放入右边的列表 right 中。
3. 递归调用 quicksort(left) 和 quicksort(right)，对左右两个子序列进行排序。由于 left 中只有三个元素，递归调用 quicksort(left) 后直接返回 [1, 2, 3]；而 right 中有五个元素，递归调用 quicksort(right) 后返回 [5, 6, 7, 8, 9]。
4. 将排序后的列表 [1, 2, 3]、比较基准点 4 和排序后的列表 [5, 6, 7, 8, 9] 按顺序合并成一个新的列表 [1, 2, 3, 4, 5, 6, 7, 8, 9]，返回结果。

over

完结撒花~此篇也算承接了很久前发过的那篇选择排序的文章(一般情况选择效率低，快排效率高)（冒泡：你再喊我？）。当然，这里排序算法就基本完结了。

所以，为啥不用.sort()排序呢？