python 快速排序

快速排序是一种基于分治法的排序算法，其基本思想是选取一个基准元素，将待排序序列划分成两个子序列，其中一个子序列中的所有元素都小于等于基准元素，另一个子序列中的所有元素都大于等于基准元素，然后对两个子序列分别进行递归排序，最终得到有序序列。

快速排序的主要步骤如下：

1. 选取一个基准元素，一般选择待排序序列的第一个元素。
2. 将序列中小于等于基准元素的元素放在基准元素的左边，大于等于基准元素的元素放在基准元素的右边。
3. 对左右两个子序列分别进行递归排序。

下面是 Python 实现快速排序的代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

在这个实现中，我们使用了 Python 的列表推导式来创建左右子序列，使用递归来进行排序。时间复杂度为 O(nlogn)。

值得注意的是，快速排序的实现方式有多种，其中包括 Hoare 和 Lomuto 两种分区方案，以及递归和迭代两种实现方式。不同的实现方式对于性能和稳定性的影响也不尽相同。