以下是常见排序算法的详细分类和解析，涵盖原理、时间复杂度及适用场景：
一、比较排序算法
1. 快速排序（Quick Sort）
- 原理：分治策略，选取基准元素（pivot），将数组分为小于基准和大于基准的两部分，递归排序。
- 时间复杂度：
- 平均：(O(n \log n))
- 最坏（已排序数组）：(O(n^2))
- 空间复杂度：(O(\log n))（递归栈）
- 稳定性：不稳定
- 代码示例：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)
2. 归并排序（Merge Sort）
- 原理：分治法，将数组递归拆分到最小单元，再合并有序子数组。
- 时间复杂度：始终 (O(n \log n))
- 空间复杂度：(O(n))（合并时需要临时数组）
- 稳定性：稳定
- 适用场景：大数据量、链表排序、外部排序（如磁盘文件排序）。
3. 堆排序（Heap Sort）
- 原理：构建最大堆，将堆顶元素（最大值）与末尾元素交换，调整堆结构。
- 时间复杂度：(O(n \log n))
- 空间复杂度：(O(1))（原地排序）
- 稳定性：不稳定
- 优势：适合实时数据流（无需全部数据即可开始排序）。
二、简单排序算法
1. 插入排序（Insertion Sort）
- 原理：逐个将元素插入已排序序列的合适位置。
- 时间复杂度：
- 平均：(O(n^2))
- 最优（已排序数组）：(O(n))
- 空间复杂度：(O(1))
- 稳定性：稳定
- 适用场景：小规模数据或基本有序数据。
2. 选择排序（Selection Sort）
- 原理：每轮找到最小元素，与当前位置交换。
- 时间复杂度：始终 (O(n^2))
- 空间复杂度：(O(1))
- 稳定性：不稳定（交换可能破坏顺序）。
3. 冒泡排序（Bubble Sort）
- 原理：相邻元素比较交换，逐步将最大值“冒泡”到末尾。
- 时间复杂度：
- 平均：(O(n^2))
- 最优（已排序数组）：(O(n))
- 空间复杂度：(O(1))
- 稳定性：稳定
三、非比较排序算法
1. 计数排序（Counting Sort）
- 原理：统计元素出现次数，按计数重建有序数组。
- 时间复杂度：(O(n + k))（(k) 为数据范围）
- 空间复杂度：(O(k))
- 适用场景：整数排序，且数据范围 (k) 较小。
2. 桶排序（Bucket Sort）
- 原理：将数据分到有限数量的桶中，每个桶单独排序后合并。
- 时间复杂度：
- 平均：(O(n + k))（(k) 为桶数量）
- 最坏：(O(n^2))
- 适用场景：数据均匀分布的场景。
3. 基数排序（Radix Sort）
- 原理：按位数从低位到高位依次进行稳定排序（如计数排序）。
- 时间复杂度：(O(d(n + k)))（(d) 为最大位数，(k) 为基数范围）
- 适用场景：整数或字符串排序。
四、算法对比与选择
| 算法 | 平均时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 快速排序 | (O(n \log n)) | (O(\log n)) | 不稳定 | 通用排序，大数据量 |
| 归并排序 | (O(n \log n)) | (O(n)) | 稳定 | 外部排序、稳定性要求高 |
| 堆排序 | (O(n \log n)) | (O(1)) | 不稳定 | 原地排序、实时数据流 |
| 插入排序 | (O(n^2)) | (O(1)) | 稳定 | 小规模或基本有序数据 |
| 计数排序 | (O(n + k)) | (O(k)) | 稳定 | 整数且范围小 |
| 基数排序 | (O(d(n + k))) | (O(n + k)) | 稳定 | 多位数整数或定长字符串 |
