实战项目9：快速排序优化¶
项目概述¶
实现和优化快速排序算法，包括基本版本、多种优化策略和不同场景的应用。这是算法竞赛中的核心算法之一，掌握快速排序的优化技巧非常重要。
学习目标¶
- 理解快速排序的原理和实现
- 掌握快速排序的多种优化策略
- 学习算法性能分析和测试
- 掌握排序算法的比较和选择
- 了解算法竞赛中的最佳实践
快速排序原理¶
基本思想¶
- 分治策略：选择一个基准元素，将数组分为两部分
- 递归排序：对左右两部分分别递归排序
- 合并结果：将排序好的部分合并
时间复杂度¶
- 最优情况：O(n log n) - 每次都能均匀分割
- 平均情况：O(n log n)
- 最坏情况：O(n²) - 数组已经有序或逆序
实现方案¶
版本1：基本实现¶
def quick_sort_basic(arr):
"""
快速排序基本实现
参数:
arr: 待排序数组
返回:
排序后的数组
"""
if len(arr) <= 1:
return arr
# 选择第一个元素作为基准
pivot = arr[0]
# 分区
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
# 递归排序并合并
return quick_sort_basic(left) + [pivot] + quick_sort_basic(right)
# 测试
test_arr = [3, 6, 8, 10, 1, 2, 1]
print(f"原数组: {test_arr}")
print(f"排序后: {quick_sort_basic(test_arr)}")
版本2：原地排序（优化内存）¶
def quick_sort_inplace(arr, low=0, high=None):
"""
快速排序原地实现
参数:
arr: 待排序数组
low: 起始索引
high: 结束索引
"""
if high is None:
high = len(arr) - 1
if low < high:
# 分区并获取基准位置
pi = partition(arr, low, high)
# 递归排序左右两部分
quick_sort_inplace(arr, low, pi - 1)
quick_sort_inplace(arr, pi + 1, high)
def partition(arr, low, high):
"""
分区函数
参数:
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
# 测试
test_arr = [3, 6, 8, 10, 1, 2, 1]
print(f"原数组: {test_arr}")
quick_sort_inplace(test_arr)
print(f"排序后: {test_arr}")
版本3：随机化基准（避免最坏情况）¶
import random
def quick_sort_randomized(arr, low=0, high=None):
"""
随机化快速排序
参数:
arr: 待排序数组
low: 起始索引
high: 结束索引
"""
if high is None:
high = len(arr) - 1
if low < high:
# 随机选择基准
random_index = random.randint(low, high)
arr[high], arr[random_index] = arr[random_index], arr[high]
pi = partition(arr, low, high)
quick_sort_randomized(arr, low, pi - 1)
quick_sort_randomized(arr, pi + 1, high)
# 测试
test_arr = [3, 6, 8, 10, 1, 2, 1]
print(f"原数组: {test_arr}")
quick_sort_randomized(test_arr)
print(f"排序后: {test_arr}")
版本4：三路快速排序（处理重复元素）¶
def quick_sort_three_way(arr, low=0, high=None):
"""
三路快速排序（Dijkstra 三路快排）
适用于大量重复元素的情况
参数:
arr: 待排序数组
low: 起始索引
high: 结束索引
"""
if high is None:
high = len(arr) - 1
if low >= high:
return
# 三路分区
lt, gt = low, high
i = low
pivot = arr[low]
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
# 递归排序小于和大于基准的部分
quick_sort_three_way(arr, low, lt - 1)
quick_sort_three_way(arr, gt + 1, high)
# 测试
test_arr = [3, 6, 3, 8, 3, 10, 1, 2, 1, 3]
print(f"原数组: {test_arr}")
quick_sort_three_way(test_arr)
print(f"排序后: {test_arr}")
版本5：插入排序优化（小数组）¶
def insertion_sort(arr, low, high):
"""
插入排序
参数:
arr: 数组
low: 起始索引
high: 结束索引
"""
for i in range(low + 1, high + 1):
key = arr[i]
j = i - 1
while j >= low and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def quick_sort_optimized(arr, low=0, high=None):
"""
优化的快速排序
优化点：
1. 小数组使用插入排序
2. 随机化基准选择
参数:
arr: 待排序数组
low: 起始索引
high: 结束索引
"""
if high is None:
high = len(arr) - 1
# 小数组使用插入排序
if high - low < 10:
insertion_sort(arr, low, high)
return
if low < high:
# 随机化基准
random_index = random.randint(low, high)
arr[high], arr[random_index] = arr[random_index], arr[high]
pi = partition(arr, low, high)
quick_sort_optimized(arr, low, pi - 1)
quick_sort_optimized(arr, pi + 1, high)
# 测试
test_arr = [3, 6, 8, 10, 1, 2, 1]
print(f"原数组: {test_arr}")
quick_sort_optimized(test_arr)
print(f"排序后: {test_arr}")
性能测试¶
测试框架¶
import time
import random
def test_sort_performance(sort_func, test_cases, name):
"""
测试排序算法性能
参数:
sort_func: 排序函数
test_cases: 测试用例列表
name: 算法名称
"""
print(f"\n=== {name} 性能测试 ===")
for size, description in test_cases:
# 生成测试数据
test_arr = [random.randint(1, 1000) for _ in range(size)]
# 复制数组
arr_copy = test_arr.copy()
# 测量时间
start_time = time.time()
sort_func(arr_copy)
end_time = time.time()
# 验证正确性
is_sorted = all(arr_copy[i] <= arr_copy[i+1] for i in range(len(arr_copy)-1))
print(f"{description} (n={size}):")
print(f" 时间: {end_time - start_time:.6f}秒")
print(f" 正确性: {'✓' if is_sorted else '✗'}")
# 测试用例
test_cases = [
(100, "小规模随机数组"),
(1000, "中等规模随机数组"),
(10000, "大规模随机数组"),
]
# 测试不同的快速排序实现
test_sort_performance(lambda arr: quick_sort_basic(arr), test_cases, "基本快速排序")
test_sort_performance(lambda arr: quick_sort_inplace(arr.copy()), test_cases, "原地快速排序")
test_sort_performance(lambda arr: quick_sort_randomized(arr.copy()), test_cases, "随机化快速排序")
test_sort_performance(lambda arr: quick_sort_optimized(arr.copy()), test_cases, "优化快速排序")
最坏情况测试¶
def test_worst_case():
"""测试最坏情况（已排序数组）"""
print("\n=== 最坏情况测试 ===")
# 创建已排序的数组
sorted_arr = list(range(1000))
# 测试随机化版本
arr1 = sorted_arr.copy()
start = time.time()
quick_sort_randomized(arr1)
time_randomized = time.time() - start
# 测试非随机化版本
arr2 = sorted_arr.copy()
start = time.time()
quick_sort_inplace(arr2)
time_non_randomized = time.time() - start
print(f"随机化版本: {time_randomized:.6f}秒")
print(f"非随机化版本: {time_non_randomized:.6f}秒")
print(f"性能提升: {time_non_randomized/time_randomized:.2f}倍")
test_worst_case()
重复元素测试¶
def test_duplicate_elements():
"""测试大量重复元素"""
print("\n=== 重复元素测试 ===")
# 创建大量重复元素的数组
test_arr = [1] * 1000 + [2] * 1000 + [3] * 1000
random.shuffle(test_arr)
# 测试普通快速排序
arr1 = test_arr.copy()
start = time.time()
quick_sort_inplace(arr1)
time_normal = time.time() - start
# 测试三路快速排序
arr2 = test_arr.copy()
start = time.time()
quick_sort_three_way(arr2)
time_three_way = time.time() - start
print(f"普通快速排序: {time_normal:.6f}秒")
print(f"三路快速排序: {time_three_way:.6f}秒")
print(f"性能提升: {time_normal/time_three_way:.2f}倍")
test_duplicate_elements()
算法竞赛最佳实践¶
竞赛模板¶
def quick_sort(arr):
"""
竞赛用快速排序模板
特点：
1. 原地排序，节省空间
2. 随机化基准，避免最坏情况
3. 简洁高效
参数:
arr: 待排序数组
返回:
排序后的数组
"""
def _quick_sort(arr, left, right):
if left >= right:
return
# 随机选择基准
pivot_idx = random.randint(left, right)
arr[right], arr[pivot_idx] = arr[pivot_idx], arr[right]
# 分区
pivot = arr[right]
i = left
for j in range(left, right):
if arr[j] < pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[right] = arr[right], arr[i]
# 递归
_quick_sort(arr, left, i - 1)
_quick_sort(arr, i + 1, right)
_quick_sort(arr, 0, len(arr) - 1)
return arr
# 使用示例
if __name__ == "__main__":
import sys
input_data = sys.stdin.read().split()
n = int(input_data[0])
arr = list(map(int, input_data[1:n+1]))
quick_sort(arr)
print(' '.join(map(str, arr)))
Python内置排序¶
# 在竞赛中，通常使用内置排序
def builtin_sort(arr):
"""
Python内置排序
Python的sort()使用Timsort算法，
时间复杂度为O(n log n)，非常高效
参数:
arr: 待排序数组
返回:
排序后的数组
"""
arr.sort()
return arr
# 或者使用sorted()返回新数组
def builtin_sort_new(arr):
"""
Python内置排序（返回新数组）
参数:
arr: 待排序数组
返回:
排序后的新数组
"""
return sorted(arr)
应用场景¶
1. 排序并返回索引¶
def sort_with_indices(arr):
"""
排序并返回原始索引
参数:
arr: 待排序数组
返回:
(排序后的数组, 原始索引数组)
"""
indexed_arr = list(enumerate(arr))
indexed_arr.sort(key=lambda x: x[1])
sorted_arr = [x[1] for x in indexed_arr]
indices = [x[0] for x in indexed_arr]
return sorted_arr, indices
# 测试
test_arr = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_arr, indices = sort_with_indices(test_arr)
print(f"原数组: {test_arr}")
print(f"排序后: {sorted_arr}")
print(f"原始索引: {indices}")
2. 多关键字排序¶
def sort_by_multiple_keys(arr, key_indices):
"""
多关键字排序
参数:
arr: 待排序数组（每个元素是元组）
key_indices: 关键字索引列表（按优先级排序）
返回:
排序后的数组
"""
arr.sort(key=lambda x: tuple(x[i] for i in key_indices))
return arr
# 测试
students = [
('张三', 90, 18),
('李四', 85, 19),
('王五', 90, 17),
('赵六', 85, 20),
]
# 先按分数降序，再按年龄升序
sorted_students = sort_by_multiple_keys(students, [1, 2])
for student in sorted_students:
print(student)
3. 自定义比较函数¶
from functools import cmp_to_key
def sort_with_comparator(arr, compare_func):
"""
使用自定义比较函数排序
参数:
arr: 待排序数组
compare_func: 比较函数
返回:
排序后的数组
"""
arr.sort(key=cmp_to_key(compare_func))
return arr
# 测试：按字符串长度排序
def compare_by_length(a, b):
if len(a) < len(b):
return -1
elif len(a) > len(b):
return 1
else:
return 0
words = ['apple', 'banana', 'cherry', 'date', 'fig']
sorted_words = sort_with_comparator(words, compare_by_length)
print(sorted_words)
优化技巧总结¶
- 随机化基准：避免最坏情况
- 小数组优化：使用插入排序
- 三路分区：处理大量重复元素
- 尾递归优化：减少递归深度
- 迭代实现：避免递归栈溢出
学习要点¶
通过这个项目，你将学习到：
- 分治算法：理解分治策略的应用
- 算法优化：掌握多种优化技巧
- 性能分析：学会测试和比较算法性能
- 边界情况：处理各种特殊输入
- 竞赛编程：掌握算法竞赛的最佳实践
相关资源¶
继续优化你的算法吧！ 掌握快速排序的各种优化技巧，为算法竞赛做好准备。