快速排序
大约 3 分钟教学文档递归与分治
快速排序
1.题目描述
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
示例 1：
输入：nums = [5,2,3,1] 输出：[1,2,3,5] 解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。 示例 2：
输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5] 解释：请注意，nums 的值不一定唯一。
2.解题思路
核心思想
快速排序采用分治法策略：
- 选择一个基准元素（pivot）
- 将数组分为两部分：小于基准的元素和大于基准的元素
- 递归地对两部分进行排序
详细步骤
1. 分区操作（Partition）
选择基准元素 → 重新排列数组 → 返回基准元素的最终位置
具体过程：
- 选择最后一个元素作为基准
- 维护一个指针指向小于基准元素的区域边界
- 遍历数组，将小于基准的元素交换到左侧
- 最后将基准元素放到正确位置
2. 递归排序
- 对基准左侧的子数组进行快速排序
- 对基准右侧的子数组进行快速排序
- 递归终止条件：子数组长度 ≤ 1
关键要点
1. 基准选择策略
- 固定位置：选择第一个或最后一个元素
- 随机选择：随机选择基准元素
- 三数取中：选择首、中、尾三个元素的中位数
2. 时间复杂度
- 最好情况：O(n log n) - 每次都能均匀分割
- 平均情况：O(n log n)
- 最坏情况：O(n²) - 每次选择的基准都是最大或最小值
3. 空间复杂度
- O(log n) - 递归调用栈的深度
快速排序是面试中的高频考点，掌握其分治思想和实现细节非常重要。
3.代码实现
def quicksort(arr, low, high):
if low < high:
# 分区操作，获得基准位置
pivot_index = partition(arr, low, high)
# 递归排序左右两部分
quicksort(arr, low, pivot_index - 1)
quicksort(arr, pivot_index + 1, high)
def partition(arr, low, high):
# 选择最后一个元素作为基准
pivot = arr[high]
# i指向小于基准的区域的边界
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
data = [5, 4, 2, 6, 3, 1]
print("原始数据为：", data)
print("-------------------------------")
quicksort(data,0,len(data)-1)
print("排序之后的数据为：",data)
print("-------------------------------")
def quicksort_simple(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_simple(left) + middle + quicksort_simple(right)
# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("原始数组:", arr)
sorted_arr = quicksort_simple(arr)
print("排序后数组:", sorted_arr)