Python 快速排序算法详解及代码实现

快速排序 (Quick Sort) 是一种高效的排序算法，它基于分治的思想，将一个大问题划分为两个小问题，分别解决这两个小问题，最终合并得到整个问题的解。

快速排序的基本思路是：选择一个元素作为基准值，将数组分成两部分，左边的部分都比基准值小，右边的部分都比基准值大，然后递归地对左右两部分进行排序。

以下是 Python 代码实现：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        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)

在这个实现中，我们首先判断数组的长度是否小于等于 1，如果是，直接返回数组。否则，我们选择数组的第一个元素作为基准值 (pivot)，并将数组分成两部分。左边部分 (left) 包含所有比基准值小的元素，右边部分 (right) 包含所有比基准值大的元素。然后，我们递归地对左右两部分进行排序，并将它们和基准值合并起来返回。

快速排序的时间复杂度为 O(nlogn)。在最坏情况下，即数组已经有序或者逆序排列时，时间复杂度为 O(n^2)。但是，由于快速排序的平均时间复杂度为 O(nlogn)，因此它仍然是一种很好的排序算法。