上篇：《排序算法的奇妙世界：如何让数据井然有序？》
个人主页：strive-debug
排序算法精讲：从理论到实践
一、排序概念及应用
1.1 基本概念
**排序**：将一组记录按照特定关键字（如数值大小）进行递增或递减排列的操作。
1.2 常见排序算法分类
- **简单低效型**：直接插入排序、冒泡排序、选择排序
- **高效优化型**：希尔排序、快速排序、归并排序、堆排序
---
二、基础排序算法实现
2.1 插入排序家族
2.1.1 直接插入排序
核心思想：将待排元素逐个插入已有序序列中。
void InsertSort(int* arr, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] > tmp) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end+1] = tmp; } }我的理解（如图所示）：
**特性分析**：
**接近有序时效率高**
时间复杂度：O(N^2)
空间复杂度：O(1)
2.1.2 希尔排序（优化版插入排序）
**优化策略**：通过分组增量（gap）预排序逐步逼近全局有序。
void ShellSort(int* arr, int n) { int gap = n; while (gap > 1) { //推荐写法：除3 gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end >= 0) { if(arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } }我的理解（如图所示）：
**特性分析**：
**突破O(N^2)的时间瓶颈**
时间复杂度：约 O(N^{1.3})
空间复杂度：O(1)
---
2.2 选择排序
直接选择排序
**核心思想**：每轮选取最小/最大值固定到序列两端。
void SelectSort(int* arr, int n) { int begin = 0, end = n - 1; while (begin < end) { int maxi = begin; int mini = begin; for (int i = begin; i <= end; i++)//end=n-1,不是n { if (arr[i] > arr[maxi]) { maxi = i;//不是arr[i] } if (arr[i] < arr[mini]) { mini = i; } } //要先判断如果maxi在开头的话，就是发生来回替换的情况 if (maxi == begin) { maxi = mini; } //循序不能乱 Swap(&arr[mini], &arr[begin]); Swap(&arr[maxi], &arr[end]); //不要忘记让end和begin，这是一个while循环 end--; begin++; } }我的理解（如图所示）：
---
2.3 交换排序
冒泡排序
经典实现+提前终止优化：
void BubbleSort(int* arr, int n) { int exchange = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { exchange = 1; Swap(&arr[j], &arr[j + 1]); } } if (exchange == 0) { break; } } }**适用场景**：
**教学演示为主，实际工程较少使用**
时间复杂度：O(N^2)
---
三、算法对比总结
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|--------------|------------------|------------|--------|------------------------|
| 直接插入排序 |O(N^2) | O(1) | ✔️ | 小规模或接近有序数据 |
| 希尔排序 |O(N^{1.3}) |O(1) | ✖️ | 中等规模数据 |
| 选择排序 |O(N^2) | O(1) | ✖️ | 教学演示 |
| 冒泡排序 |O(N^2) | O(1) | ✔️ | 理解交换思想 |
---
**四、下篇预告**
**《高阶排序算法：分治思想与性能突破》**
- **快速排序的三种分区策略**
- **归并排序的递归与非递归实现**
- **堆排序与优先队列的深度关联**
---
