快速排序 - 元素码农

发布时间: 2025-03-21 18:41

↑

# 快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法的思想。它通过选择一个基准元素（pivot），将数组分为两个子数组，一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。

## 基本原理

1. 选择基准元素（pivot）
2. 将数组分区（partition）：
   - 将小于基准的元素移到左边
   - 将大于基准的元素移到右边
3. 递归排序左右子数组

## 动画演示

```
初始数组：[ 7 2 1 6 8 5 3 4 ]

选择基准元素 4：
[ 7 2 1 6 8 5 3 4 ]

第一次分区：
[ 2 1 3 4 8 5 7 6 ]  // 4 作为基准

递归左边：[ 2 1 3 ]
选择基准元素 2：
[ 1 2 3 ]  // 已排序

递归右边：[ 8 5 7 6 ]
选择基准元素 6：
[ 5 6 8 7 ]  // 继续递归

最终结果：[ 1 2 3 4 5 6 7 8 ]
```

## 代码实现

### 基本实现

```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]
print("排序前:", arr)
sorted_arr = quick_sort(arr)
print("排序后:", sorted_arr)
```

### 原地排序版本

```python
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, high):
    if low < high:
        # 获取分区点
        pi = partition(arr, low, high)
        
        # 递归排序左右子数组
        quick_sort_inplace(arr, low, pi - 1)
        quick_sort_inplace(arr, pi + 1, high)

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
quick_sort_inplace(arr, 0, len(arr) - 1)
print("排序后:", arr)
```

### 优化版本

```python
def get_pivot(arr, low, high):
    # 三数取中法选择基准
    mid = (low + high) // 2
    pivot = high
    
    if arr[low] < arr[mid]:
        if arr[mid] < arr[high]:
            pivot = mid
    elif arr[low] < arr[high]:
        pivot = low
    
    return pivot

def partition_optimized(arr, low, high):
    pivot_index = get_pivot(arr, low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    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_optimized(arr, low, high):
    while low < high:
        if high - low + 1 < 10:
            # 小数组使用插入排序
            insertion_sort(arr, low, high)
            break
        else:
            # 获取分区点
            pi = partition_optimized(arr, low, high)
            
            # 对较小的子数组进行递归
            if pi - low < high - pi:
                quick_sort_optimized(arr, low, pi - 1)
                low = pi + 1
            else:
                quick_sort_optimized(arr, pi + 1, high)
                high = pi - 1

def insertion_sort(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

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
print("排序前:", arr)
quick_sort_optimized(arr, 0, len(arr) - 1)
print("排序后:", arr)
```

## 性能分析

### 时间复杂度

- 最好情况：O(n log n)，每次都能平均分区
- 最坏情况：O(n²)，已经有序或逆序时
- 平均情况：O(n log n)

### 空间复杂度

- 基本实现：O(n)，需要额外空间
- 原地排序：O(log n)，递归调用栈

### 稳定性

- 不稳定排序算法
- 相等元素的相对位置可能改变

## 优化策略

1. 基准元素选择
   - 三数取中法
   - 随机选择
   - 九数取中法

2. 小数组优化
   - 对于小规模数组使用插入排序
   - 一般阈值设为5-15

3. 重复元素处理
   - 三路快排
   - 双轴快排

## 应用场景

1. 大规模数据排序
2. 内部排序首选算法
3. 平均性能要求高的场景
4. 递归实现简单的场景

## 实际应用示例

### 1. 文件大小排序

```python
from pathlib import Path

class FileInfo:
    def __init__(self, path):
        self.path = path
        self.size = path.stat().st_size
    
    def __str__(self):
        return f"{self.path.name}: {self.size} bytes"

def sort_files_by_size(directory):
    files = [FileInfo(f) for f in Path(directory).glob("*") if f.is_file()]
    
    def quick_sort(files, low, high):
        if low < high:
            pivot = files[high].size
            i = low - 1
            
            for j in range(low, high):
                if files[j].size <= pivot:
                    i += 1
                    files[i], files[j] = files[j], files[i]
            
            files[i + 1], files[high] = files[high], files[i + 1]
            pi = i + 1
            
            quick_sort(files, low, pi - 1)
            quick_sort(files, pi + 1, high)
    
    quick_sort(files, 0, len(files) - 1)
    return files

# 使用示例
directory = "./documents"
print("文件按大小排序:")
for file in sort_files_by_size(directory):
    print(file)
```

### 2. 自定义对象排序

```python
class Task:
    def __init__(self, name, priority, deadline):
        self.name = name
        self.priority = priority
        self.deadline = deadline
    
    def __str__(self):
        return f"{self.name} (优先级:{self.priority}, 截止日期:{self.deadline})"

def sort_tasks(tasks):
    def quick_sort(tasks, low, high):
        if low < high:
            # 使用优先级作为主要排序依据
            pivot = tasks[high].priority
            i = low - 1
            
            for j in range(low, high):
                if tasks[j].priority >= pivot:
                    i += 1
                    tasks[i], tasks[j] = tasks[j], tasks[i]
            
            tasks[i + 1], tasks[high] = tasks[high], tasks[i + 1]
            pi = i + 1
            
            quick_sort(tasks, low, pi - 1)
            quick_sort(tasks, pi + 1, high)
    
    quick_sort(tasks, 0, len(tasks) - 1)
    return tasks

# 使用示例
from datetime import datetime, timedelta

tasks = [
    Task("项目报告", 3, datetime.now() + timedelta(days=2)),
    Task("代码审查", 1, datetime.now() + timedelta(days=1)),
    Task("Bug修复", 2, datetime.now() + timedelta(days=3)),
    Task("团队会议", 2, datetime.now() + timedelta(days=1)),
    Task("系统部署", 3, datetime.now())
]

print("任务排序前:")
for task in tasks:
    print(task)

sort_tasks(tasks)

print("\n按优先级排序后:")
for task in tasks:
    print(task)
```

## 总结

快速排序是一种高效的比较排序算法，它的主要特点是：

1. 平均时间复杂度为O(n log n)，性能优秀
2. 原地排序，空间复杂度低
3. 不稳定排序，但影响较小
4. 适合大规模数据排序

通过合理的优化（如三数取中、小数组优化等），快速排序可以在实际应用中获得更好的性能。它是各种编程语言标准库中排序算法的首选实现之一，在系统级应用和大规模数据处理中广泛使用。