快速排序算法python

以下是Python实现的快速排序算法：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]  # 选择中间的元素作为枢轴
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

在这个实现中，我们首先检查数组的长度是否小于或等于1。如果是，我们就可以直接返回数组。否则，我们选择数组中间的元素作为枢轴。然后我们将数组中小于枢轴的所有元素放入左侧列表中，等于枢轴的元素放入中间列表中，大于枢轴的元素放入右侧列表中。最后，我们递归地对左侧和右侧列表进行快速排序，然后将它们与中间列表合并起来。

快速排序的时间复杂度为O(nlogn)，其中n是数组的长度。由于快速排序是一个原地排序算法，它的空间复杂度是O(1)。