💻
计算机
如何在Python中实现快速排序算法？
问题描述
请提供一个用Python实现的快速排序算法代码示例，并简要说明其工作原理。
问题解答
以下是Python实现的快速排序算法代码示例：
```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 = [3, 6, 8, 10, 1, 2, 1]
print("排序前:", arr)
print("排序后:", quick_sort(arr))
```
工作原理：
1. 选择基准值（pivot）：通常选取数组中间的元素
2. 分区操作：将数组分为三部分 - 小于基准值的元素、等于基准值的元素和大于基准值的元素
3. 递归排序：对小于和大于基准值的子数组递归调用快速排序
4. 合并结果：将排序好的子数组与基准值合并
快速排序的平均时间复杂度为O(n log n)，最坏情况为O(n²)。