# 01-排序算法

## 💡 核心结论

### 排序算法本质
- **目标**：将无序数据按某种规则排列成有序
- **关键指标**：时间复杂度、空间复杂度、稳定性
- **稳定性**：相等元素排序后相对位置不变
- **选择**：根据数据规模、是否原地、是否稳定来选择

### 算法对比（必须记住）
| 算法 | 平均 | 最坏 | 最好 | 空间 | 稳定 | 适用场景 |
|------|------|------|------|------|------|----------|
| 冒泡 | O(n²) | O(n²) | O(n) | O(1) | ✅ | 小规模、教学 |
| 选择 | O(n²) | O(n²) | O(n²) | O(1) | ❌ | 写操作代价高 |
| 插入 | O(n²) | O(n²) | O(n) | O(1) | ✅ | 小规模、近似有序 |
| 希尔 | O(n^1.3) | O(n²) | O(n) | O(1) | ❌ | 中等规模 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | 稳定排序、链表 |
| 快排 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌ | **通用首选** |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | 原地排序 |
| 计数 | O(n+k) | O(n+k) | O(n+k) | O(k) | ✅ | 整数、范围小 |
| 桶排序 | O(n+k) | O(n²) | O(n) | O(n+k) | ✅ | 均匀分布 |
| 基数 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | ✅ | 多关键字 |

### 选择建议
- **通用场景**：快速排序（平均最快）
- **需要稳定**：归并排序
- **空间受限**：堆排序（原地）
- **小规模**：插入排序（常数小）
- **近似有序**：插入排序
- **整数范围小**：计数排序
- **链表排序**：归并排序

### 核心思想
- **比较排序**：通过比较决定顺序，下界O(n log n)
- **非比较排序**：利用特殊性质，可以O(n)
- **分治思想**：归并、快排
- **减治思想**：插入、选择
- **堆结构**：堆排序

## 🔵 冒泡排序

### 原理
重复遍历，比较相邻元素，逆序则交换，每次把最大元素"冒泡"到末尾。

### 时间复杂度
- 最好：O(n) - 已有序，一次遍历
- 平均：O(n²)
- 最坏：O(n²) - 逆序

### 优化
- 添加flag：一轮没交换则提前结束
- 记录最后交换位置：减少比较次数

## 🔴 选择排序

### 原理
每次从未排序部分选择最小元素，放到已排序部分末尾。

### 时间复杂度
- 始终O(n²)，无论数据状态
- 交换次数O(n)，少于冒泡

## 🟡 插入排序

### 原理
将元素插入到已排序部分的正确位置。

### 时间复杂度
- 最好：O(n) - 已有序
- 平均：O(n²)
- 适合小规模或近似有序数据

## 🟢 归并排序

### 原理
分治策略：分割→递归排序→合并。

### 特点
- **稳定排序**
- **时间稳定**：O(n log n)
- **空间O(n)**：需要额外数组
- **适合链表**：不需要随机访问

### 应用
- 外部排序
- 求逆序对
- 链表排序

## 🟣 快速排序

### 原理
选择pivot，分区使左边<pivot，右边>pivot，递归排序。

### 特点
- **平均最快**：O(n log n)
- **最坏O(n²)**：已排序数据，需要随机化或三数取中
- **原地排序**：空间O(log n)递归栈
- **不稳定**

### 优化
- 三数取中选pivot
- 小规模用插入排序
- 三路快排处理重复元素

## 🟠 堆排序

### 原理
建最大堆，反复取堆顶放到末尾，调整堆。

### 特点
- **时间稳定**：O(n log n)
- **原地排序**：O(1)额外空间
- **不稳定**

## ⚪ 非比较排序

### 计数排序
- **适用**：整数，范围k不大（k < n log n）
- **时间**：O(n + k)
- **空间**：O(k)
- **稳定**

### 桶排序
- **适用**：数据均匀分布
- **时间**：O(n)（理想情况）
- **空间**：O(n + k)

### 基数排序
- **适用**：多关键字排序
- **时间**：O(d(n + k))，d为位数
- **空间**：O(n + k)

## 🎯 经典应用

### 1. 第K大元素
```python
# 快速选择：O(n)平均
def findKthLargest(nums, k):
    return quickSelect(nums, len(nums) - k)

# 堆：O(n log k)
def findKthLargest(nums, k):
    return heapq.nlargest(k, nums)[-1]
```

### 2. 数组中的第K个最大元素
快速选择 > 堆 > 排序

### 3. 合并K个有序链表
最小堆：O(n log k)

### 4. 求逆序对
归并排序：O(n log n)

## 📚 LeetCode练习

### 基础
- [912. Sort an Array](https://leetcode.com/problems/sort-an-array/)
- [75. Sort Colors](https://leetcode.com/problems/sort-colors/)

### 应用
- [215. Kth Largest Element](https://leetcode.com/problems/kth-largest-element-in-an-array/)
- [23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
- [148. Sort List](https://leetcode.com/problems/sort-list/)
- [493. Reverse Pairs](https://leetcode.com/problems/reverse-pairs/)

## 💡 面试建议

### 必须手写
- 快速排序
- 归并排序
- 堆排序

### 必须理解
- 时间复杂度分析
- 稳定性的应用
- 优化技巧

### 常见问题
- **为什么快排平均最快？**
  - 缓存友好、原地排序、常数因子小
  
- **什么时候用归并？**
  - 需要稳定性、链表排序、外部排序
  
- **堆排序的优势？**
  - 原地、最坏O(n log n)、适合Top K

## 🔧 优化技巧

### 1. 小规模用插入
```python
if len(arr) < 10:
    insertion_sort(arr)
```

### 2. 快排优化
- 随机化pivot
- 三数取中
- 三路快排

### 3. 混合排序
```python
# 归并排序 + 插入排序
def merge_sort(arr):
    if len(arr) < 10:
        return insertion_sort(arr)
    # 继续归并
```

## 🎯 总结

排序是算法基础，务必掌握：
1. **理解原理**：每种排序的核心思想
2. **手写实现**：至少快排、归并、堆排序
3. **复杂度分析**：时间、空间、稳定性
4. **应用场景**：知道何时用何种排序
5. **优化技巧**：混合排序、随机化等

## 💻 完整代码实现

### Python 实现

```{literalinclude} sorting.py
:language: python
:linenos:
```

### C++ 实现

```{literalinclude} sorting.cpp
:language: cpp
:linenos:
```