五大经典排序算法详解
排序是数据结构与算法中最基础也最重要的操作之一。今天咱们来聊聊五种最经典的排序算法：插入、希尔、冒泡、选择和堆排序。我会结合代码和实际场景，带大家理清它们的核心逻辑与性能差异。
插入排序
核心思想
插入排序的思路非常直观，就像我们整理扑克牌一样。把数组分成'已排序'和'未排序'两部分，初始时已排序部分只包含第一个元素。每次从未排序部分取出一个元素，向前插入到已排序序列的正确位置，保持整体有序。重复这个过程直到所有元素归位。
代码实现
void InsertSort(int* a, int n) {
// 遍历未排序元素（从第 2 个元素开始）
for (int i = 1; i < n; i++) {
int end = i - 1; // 已排序部分末尾下标
int tmp = a[i]; // 保存当前待插入元素
// 向前查找合适位置，大于 tmp（降序）则后移
while (end >= 0) {
if (a[end] < tmp) {
a[end + 1] = a[end]; // 元素后移腾位置
end--;
} else {
break; // 找到位置，退出循环
}
}
a[end + 1] = tmp; // 插入到正确位置
}
}
注意：上述代码演示的是降序排列，若要升序只需将判断条件 a[end] < tmp 改为 a[end] > tmp。
效率分析
- 时间复杂度：最坏情况下需要比较 N²/2 次，为 O(N²)。但如果数组已经基本有序，每个元素只需比较 1 次，可优化至 O(N)。
- 空间复杂度：仅使用常数级辅助变量，O(1)。
- 稳定性：稳定。相等元素的相对位置在插入过程中不会改变。
希尔排序
核心思想
希尔排序可以看作是插入排序的升级版。它通过设定一个增量（步长），将数组分割成若干子序列进行分组插入排序。随着增量逐渐缩小，数组整体变得'基本有序'，最后当增量为 1 时，进行一次标准的插入排序，此时效率极高。
代码实现
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1; /* 常用增量序列 */
/* 多组并排 */
for (int j = 0; j < gap; j++) {
for (int i = j; i < n - gap; i += gap) {
int end = i;
int tmp = a[i + gap];
while (end >= 0) {
if (tmp > a[end]) { /* 降序调整 */
a[end + gap] = a[end];
end -= gap;
} else {
break;
}
}
a[end + gap] = tmp;
}
}
}
}
效率分析
- 时间复杂度：取决于增量序列的选择。通常认为介于 O(NlogN) 和 O(N²) 之间，常归为 O(NlogN) 量级。
- 空间复杂度：O(1)。
- 稳定性：不稳定。跳跃式交换可能破坏相同值元素的原始相对顺序。
选择排序
核心思想
选择排序的核心是'挑最小'。每次从未排序部分选出最小（或最大）的元素，与未排序部分的第一个元素交换。重复此过程，直到整个数组有序。
代码实现
这里展示一种双向选择排序的优化版本，每轮同时找出最大值和最小值，分别放到两端。
void SelectSort(int* a, int n) {
int left = 0;
int right = n - 1;
while (left < right) {
int max = left;
int min = left;
for (int i = left + 1; i <= right; i++) {
if (a[max] < a[i]) {
max = i;
}
if (a[min] > a[i]) {
min = i;
}
}
swap(&a[left], &a[min]);
// 修正：max 有可能和 left 重叠
if (left == max) {
max = min;
}
swap(&a[right], &a[max]);
left++;
right--;
}
}
效率分析
- 时间复杂度：无论数据是否有序，都需要遍历比较，固定为 O(N²)。
- 空间复杂度：O(1)。
- 稳定性：不稳定。交换操作可能打乱相等元素的顺序。
堆排序
核心思想
堆排序利用二叉堆的特性。首先将数组构建为大顶堆（或小顶堆），堆顶即为当前最大值。将堆顶与末尾元素交换，使最大值归位，然后重新调整剩余元素为堆。重复此过程直至有序。
代码实现
// 向下调整算法
void AdjustDown(int* a, int n, int parent) {
int child = 2 * parent + 1;
while (child < n) {
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
if (a[child] > a[parent]) {
swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
// 堆排序
void HeapSort(int* a, int n) {
// 向下调整建堆 -- O(N)
for (int i = (n - 2) / 2; i >= 0; i--) {
AdjustDown(a, n, i);
}
// 排序阶段
int end = n - 1;
while (end > 0) {
swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
效率分析
- 时间复杂度：建堆 O(N)，排序阶段 N 次调整每次 O(logN)，总体 O(NlogN)。不受数据分布影响。
- 空间复杂度：O(1)。
- 稳定性：不稳定。堆调整过程中的交换会改变相等元素的相对位置。
冒泡排序
核心思想
冒泡排序通过相邻元素的比较与交换，让较大（或较小）的元素逐步'浮'到数组末尾。每一轮遍历后，当前未排序部分的最大值会被推到末尾。
代码实现
void BubbleSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int flag = 0; // 标记本轮是否发生交换
for (int j = 1; j < n - i; j++) {
if (a[j - 1] > a[j]) {
swap(&a[j - 1], &a[j]);
flag = 1;
}
}
if (flag == 0) {
break; // 若本轮无交换，说明已有序，提前结束
}
}
}
效率分析
- 时间复杂度：常规情况 O(N²)，加入提前终止优化后，最好情况（已有序）可达 O(N)。
- 空间复杂度：O(1)。
- 稳定性：稳定。仅在严格大于时才交换。
性能对比总结
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 插入排序 | O(N²) | O(N²) | O(1) | 稳定 |
| 希尔排序 | O(NlogN) | O(N²) | O(1) | 不稳定 |
| 选择排序 | O(N²) | O(N²) | O(1) | 不稳定 |
| 堆排序 | O(NlogN) | O(NlogN) | O(1) | 不稳定 |
| 冒泡排序 | O(N²) | O(N²) | O(1) | 稳定 |
在实际开发中，如果数据量小或部分有序，插入排序往往表现优异；对于大规模数据，堆排序或希尔排序的效率更高。选择排序虽然简单但效率较低，通常不作为首选。冒泡排序因易于理解和优化，常用于教学或特定小规模场景。理解这些算法的底层逻辑，有助于我们在不同场景下做出更合适的选择。