您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 如何实现快速排序
## 引言
快速排序(Quick Sort)是计算机科学中最经典的排序算法之一,由英国计算机科学家托尼·霍尔(Tony Hoare)于1959年提出。作为分治法(Divide and Conquer)的典型应用,快速排序因其平均时间复杂度为O(n log n)而成为实际应用中最快的通用排序算法之一。本文将深入探讨快速排序的原理、实现步骤、优化策略以及实际应用场景。
## 快速排序的基本原理
### 算法思想
快速排序的核心思想是通过一次排序(称为分区操作)将待排序数据分割成独立的两部分:
1. **左子序列**:所有元素小于等于基准值(pivot)
2. **右子序列**:所有元素大于基准值
然后递归地对这两个子序列进行快速排序,最终得到有序序列。
### 关键步骤
1. **选择基准值(Pivot Selection)**:从数组中选择一个元素作为比较基准
2. **分区操作(Partitioning)**:重新排列数组使小于基准的元素位于其左侧,大于基准的位于右侧
3. **递归排序(Recursion)**:对左右子数组递归应用相同操作
## 实现细节
### 基础实现(以升序为例)
```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)
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
def quick_sort_inplace(arr, low=0, high=None):
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)
不同的基准选择方式会显著影响算法性能:
策略 | 描述 | 时间复杂度 | 适用场景 |
---|---|---|---|
固定位置 | 总是选择第一个/最后一个元素 | 最坏O(n²) | 不推荐 |
随机选择 | 随机选取元素作为基准 | 平均O(n log n) | 通用场景 |
三数取中 | 选择首、中、尾的中位数 | 优化最坏情况 | 基本有序数据 |
中位数的中位数 | 更复杂的选择方法 | 保证O(n log n) | 极端情况 |
以数组 [10, 80, 30, 90, 40, 50, 70]
为例:
场景 | 时间复杂度 | 说明 |
---|---|---|
最优情况 | O(n log n) | 每次分区平衡 |
平均情况 | O(n log n) | 随机分布数据 |
最坏情况 | O(n²) | 已排序数据+固定基准 |
算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
---|---|---|---|---|
快速排序 | O(n log n) | O(log n) | 不稳定 | 通用排序 |
归并排序 | O(n log n) | O(n) | 稳定 | 需要稳定性 |
堆排序 | O(n log n) | O(1) | 不稳定 | 空间受限 |
Timsort | O(n log n) | O(n) | 稳定 | Python/Java内置 |
std::sort()
:通常采用快速排序+插入排序混合Arrays.sort()
:对基本类型使用快速排序变体list.sort()
:使用Timsort算法不是。分区过程中相等元素的相对位置可能改变。
可采用三路分区(Dutch National Flag)方法:
def quick_sort_3way(arr, low, high):
if low >= high:
return
lt, gt = low, high
pivot = arr[low]
i = 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[gt], arr[i] = arr[i], arr[gt]
gt -= 1
else:
i += 1
quick_sort_3way(arr, low, lt-1)
quick_sort_3way(arr, gt+1, high)
虽然两者都是O(n log n),但快速排序的: 1. 常数因子更小 2. 内存访问模式更友好(局部性原理) 3. 原地排序特性减少内存分配
快速排序作为高效排序算法的代表,其核心优势在于: 1. 平均情况下的优异性能 2. 原地排序的内存效率 3. 适应不同数据特征的优化空间
掌握快速排序不仅有助于理解分治算法思想,也是面试中常考的重点算法。建议读者通过可视化工具观察排序过程,并尝试实现不同变体来加深理解。
“快速排序的魅力在于其简洁而强大的分治策略,将复杂问题优雅地分解为可管理的子问题。” —— 算法导论 “`
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。