快速排序
快速排序是一种分治算法，通过选择一个基准元素将数组分成两部分，然后递归排序。
概述
快速排序是高效的排序算法，平均时间复杂度为 O(n log n)。
算法步骤
- 选择基准元素: 通常选择中间元素
- 分区: 将数组分成小于基准和大于基准的两部分
- 递归排序: 对两部分分别进行排序
实现
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]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print(sorted_arr) # [11, 12, 22, 25, 34, 64, 90]原地排序版本
python
def quick_sort_in_place(arr, low, high):
if low < high:
pivot_idx = partition(arr, low, high)
quick_sort_in_place(arr, low, pivot_idx - 1)
quick_sort_in_place(arr, pivot_idx + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort_in_place(arr, 0, len(arr) - 1)
print(arr) # [11, 12, 22, 25, 34, 64, 90]复杂度分析
| 情况 | 时间复杂度 |
|---|---|
| 平均 | O(n log n) |
| 最好 | O(n log n) |
| 最坏 | O(n²) |
空间复杂度
- 递归版本：O(log n)
- 原地版本：O(log n)（递归栈）
优化策略
三数取中
python
def median_of_three(arr, low, high):
mid = (low + high) // 2
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
return mid小数组使用插入排序
python
def quick_sort_optimized(arr, low, high):
if high - low + 1 < 10:
insertion_sort(arr, low, high)
return
pivot_idx = median_of_three(arr, low, high)
arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
pivot_idx = partition(arr, low, high)
quick_sort_optimized(arr, low, pivot_idx - 1)
quick_sort_optimized(arr, pivot_idx + 1, high)应用场景
- 通用排序场景
- 需要平均性能好的排序
- 不需要稳定排序的场景
与其他排序算法对比
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 |