排序算法全解析:从基础原理到动画可视化实战
基本概念与评价指标
排序的本质是重新排列数据,使其满足单调性(通常是递增或递减)。在实际业务中,无论是电商的商品推荐、社交网络的好友排序,还是数据库的索引构建,高效的排序都是性能优化的基石。
评价指标
评价一个排序算法的好坏,主要看以下几个维度:
- 时间复杂度:算法执行所需的基本操作次数,通常关注平均和最坏情况。
- 空间复杂度:算法运行过程中额外占用的内存空间。
- 稳定性:若待排序表中有两个元素关键字相同,排序后它们的相对位置保持不变,则称该算法稳定。这在需要保留原始顺序的场景(如按成绩排序后保持姓名顺序)至关重要。
- 适应性:针对特定输入序列(如基本有序)的性能表现。
分类概览
- 内部排序:数据全部在内存中处理,关注时、空复杂度。
- 外部排序:数据量过大无法一次性装入内存,需借助外存(磁盘),重点关注 I/O 开销。
内部排序算法详解
1. 插入类排序
直接插入排序
这是最基础的排序方式,思想类似于整理扑克牌。每次将一个待排序的记录插入到前面已排好序的子序列中。
为了优化边界判断,我们常引入哨兵。哨兵不仅简化了代码逻辑,还能减少数组越界检查的次数。
// 带哨兵的直接插入排序
void InsertSort(int A[], int n) {
int i, j;
for (i = 2; i <= n; i++) { // 依次将 A[2]~A[n] 插入到前面已排序序列
if (A[i] < A[i - 1]) { // 若 A[i] 关键码小于其前驱
A[0] = A[i]; // 复制为哨兵,A[0] 不存放元素
for (j = i - 1; A[0] < A[j]; --j)
A[j + 1] = A[j]; // 向后挪位
A[j + 1] = A[0]; // 复制到插入位置
}
}
}
效率分析:
- 空间复杂度:O(1)
- 时间复杂度:最好 O(n),最坏 O(n²)
- 稳定性:稳定


