排序算法是算法的“基石”——你可以在不了解其他算法的情况下写出程序，但没有排序算法，你连二分查找都跑不起来。理解排序算法，就是理解整个算法思维的开端。
一、排序算法基础：重新认识“排序”
1.1 什么是排序算法？
排序算法的核心目标很简单：将一组数据按照特定顺序（通常是升序或降序）重新排列。但“简单”的目标下，隐藏着计算机科学中最丰富、最深刻的问题域。
从1945年冯·诺依曼提出归并排序至今，排序算法已经演变为一个庞大的算法家族——每种算法都代表了不同的计算机科学思想：
插入排序代表“增量构建”
归并排序代表“分治策略”
堆排序代表“优先队列抽象”
快速排序代表“随机化与概率”
基数排序代表“非比较排序”
核心指标：排序算法的优劣通常用三个维度衡量——时间复杂度、空间复杂度和稳定性。
1.2 稳定性：一个容易被忽视的关键特性
稳定排序指：如果两个元素相等，排序后它们的相对顺序保持不变。稳定性的价值在于——当你要对复杂对象按多个字段排序时，逐次稳定排序可以叠加排序结果。
1.3 算法分类总览
| 分类 | 代表算法 | 核心思想 |
|---|---|---|
| 简单排序 | 冒泡、选择、插入 | 易于理解，适合小规模数据 |
| 高效排序 | 快速、归并、堆 | 利用分治或堆结构，O(n log n) |
| 线性时间排序 | 计数、基数、桶 | 非比较排序，利用数据分布特性 |
| 混合排序 | Timsort | 结合插入和归并，自适应优化 |
| 并行/分布式 | Bitonic排序 | 利用多核/多机并行 |
二、经典排序算法深度解析
2.1 冒泡排序：最直观的排序
思想：重复遍历数列，每次比较相邻元素，将较大的“冒泡”到末尾。
c
void bubble_sort(int arr[], int n) { for (int i = 0; i < n-1; i++) { int swapped = 0; for (int j = 0; j < n-1-i; j++) { if (arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); swapped = 1; } } if (!swapped) break; // 提前终止优化 } }复杂度：O(n²)时间，O(1)空间，稳定。
特点：简单易实现，小规模数据可用。优化后，当数据已基本有序时，时间复杂度可降至O(n)。
2.2 插入排序：打扑克牌的思维方式
思想：将元素逐一插入到已经排序好的序列中的正确位置。
c
void insertion_sort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }