请帮我用Python写一个快速排序算法
快速排序（Quick Sort）是一种高效的排序算法，采用分治策略。以下是 Python 实现：
def quicksort(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 quicksort(left) + middle + quicksort(right)
时间复杂度分析：
非常好！能不能再给出一个堆排序的版本？
好的，以下是堆排序（Heap Sort）的 Python 实现：
def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n = len(arr) # Build max heap for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr
堆排序优势：时间复杂度始终为 O(n log n)，不需要额外空间（原地排序），最坏情况和平均情况性能一致。相比快排序，堆排序不存在退化到 O(n²) 的风险。