python递归实现快速排序

Python递归实现快速排序

快速排序是一种常用的排序算法，递归是快速排序算法的重要部分。

快速排序算法步骤

1. 选择一个基准数（pivot）。
2. 将待排序数组分成左右两个子数组，小于等于基准数的元素放在左边，大于基准数的元素放在右边。
3. 递归地对左右两个子数组进行上述排序过程。

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] #小于pivot的元素放入left列表中
    middle = [x for x in arr if x == pivot] #等于pivot的元素放入middle列表中
    right = [x for x in arr if x > pivot] #大于pivot的元素放入right列表中
    return quick_sort(left) + middle + quick_sort(right) #递归调用快速排序，最后将三个列表合并

arr = [3,6,1,2,7,9,4,5,8]
print(quick_sort(arr))

示例说明

示例一

输入：arr = [3,6,1,2,7,9,4,5,8]

输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

解释：

首先选取中间的数pivot=5，遍历数组，小于5的数放在left数组中，等于5的数放在middle数组中，大于5的数放在right数组中。数组变成了[3,1,2,4] + [5] + [6,7,9,8]。递归调用快速排序quick_sort(left), quick_sort(right)，直到left和right数组长度为1。最后将三个列表拼接起来即可。

示例二

输入：arr = [7,4,8,1,2,9,3,6,5]

输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

解释：

首先选取中间的数pivot=3，遍历数组，小于3的数放在left数组中，等于3的数放在middle数组中，大于3的数放在right数组中。数组变成了[1,2] + [3] + [7,4,8,9,6,5]。递归调用快速排序quick_sort(left), quick_sort(right)，直到left和right数组长度为1。最后将三个列表拼接起来即可。