python-快速排序算法

快速排序算法是一种常见的排序算法，时间复杂度为O(n log n)。它通过分治思想将一个大问题分解成多个小问题，然后逐步解决小问题，最终得到整个问题的解。

快速排序的基本思想是：选择一个基准元素，将序列分成两个子序列，小于等于基准元素的放在左边，大于基准元素的放在右边，然后递归地对左右子序列进行排序，最终得到有序序列。

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

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    left_nums = [num for num in nums if num < pivot]
    mid_nums = [num for num in nums if num == pivot]
    right_nums = [num for num in nums if num > pivot]
    return quick_sort(left_nums) + mid_nums + quick_sort(right_nums)

在这个实现中，我们首先检查序列是否为空或只包含一个元素，如果是，则返回序列本身。否则，我们选择一个基准元素（这里我们选择中间元素），并将序列分成三个子序列：小于基准元素的序列、等于基准元素的序列和大于基准元素的序列。然后，我们递归地对左右子序列进行排序，并将三个子序列合并成一个有序序列返回。

这是一个简单的实现，但它的空间复杂度为O(n)，因为它使用了额外的存储空间来存储左右子序列和中间元素。如果我们想要原地排序，我们可以使用“原地分区”和“尾递归”来优化算法。