实现快速排序（Quicksort）

在 Python 3.11 中，实现快速排序（Quicksort）可以通过递归的方式。快速排序是一种分治算法，基本思想是通过选择一个基准元素，将数组分成两部分，一部分比基准元素小，另一部分比基准元素大，然后递归地排序这两部分。

下面是一个简单的 Python 3.11 快速排序实现：

快速排序实现

def quicksort(arr):# 如果数组长度为 0 或 1，直接返回（递归基准条件）if len(arr) <= 1:return arr# 选择基准元素（可以选择任意一个，这里选择最后一个元素）pivot = arr[-1]# 分割数组，小于基准的放在左边，大于基准的放在右边left = [x for x in arr[:-1] if x <= pivot]right = [x for x in arr[:-1] if x > pivot]# 递归排序左右两边return quicksort(left) + [pivot] + quicksort(right)# 测试
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quicksort(arr)
print(sorted_arr)  # 输出 [1, 1, 2, 3, 6, 8, 10]

解释

• 基准条件：当数组长度为 0 或 1 时，数组是有序的，可以直接返回。
• 分割数组：选择最后一个元素作为基准 pivot，将小于或等于 pivot 的元素放到 left，将大于 pivot 的元素放到 right。
• 递归排序：对 left 和 right 递归调用 quicksort 函数，最终将 left + pivot + right 拼接成一个新的数组。

时间复杂度分析

• 最坏情况时间复杂度是 O(n²)，当每次分割都非常不均匀时会出现这种情况，比如数组已经有序时总是选到最大或最小元素作为基准。
• 平均时间复杂度是 O(n log n)，在大多数情况下，快速排序的性能是非常优秀的。

优化建议

可以对基准的选择进行优化，如使用“三数取中法”（Median of Three）来选取基准元素，这样可以减少最坏情况发生的概率。