快速排序

快速排序（QuickSort）是一种常用的排序算法，也是一种分治算法。它将一个数组分成两个子数组，然后递归地排序两个子数组。具体实现步骤如下：

1. 选择一个基准元素（pivot），一般选择第一个元素或者最后一个元素。
2. 将所有小于基准元素的元素移到基准元素的左边，将所有大于基准元素的元素移到基准元素的右边，这个过程称为分区（partition）。
3. 递归地对基准元素左边的子数组和右边的子数组进行快速排序。

具体的实现代码如下（以升序排序为例）：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left) + [pivot] + quick_sort(right)

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。