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)

# 示例
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print(sorted_arr)  # 输出 [1, 1, 2, 3, 6, 8, 10]

在这个示例代码中，quick_sort函数使用递归来对输入的arr进行排序。它首先选择一个基准值（pivot），将数组划分成小于、等于和大于基准值的三部分。然后，对小于和大于部分再分别调用quick_sort函数，递归地进行排序。最后，将排好序的左、中、右三个部分合并起来返回最终结果。注意在递归调用时，需要确保基准值所在的middle部分不再参与排序，以避免死循环。

快速排序的平均时间复杂度为O(nlogn)，但在最坏情况下可能达到O(n^2)。然而，由于它的常数因子较小，实际应用中它通常表现良好。