前言
排序是数据处理中最基础且重要的操作之一。其核心目标是将一组数据元素按照特定关键字（如数值大小、字母顺序）重新排列成有序序列，以满足升序或降序的要求。排序广泛应用于数据库查询优化、任务调度、数据可视化等场景。
概念辨析
在深入具体算法前，我们需要明确几个关键分类标准：
比较排序 vs 非比较排序
- 比较排序：依赖元素间的大小比较（
>、<、==）来确定顺序。适用于任意可比较类型的数据。理论下限为 O(n log n)。 - 非比较排序：利用元素值的特性（如范围、频率）直接计算位置。通常仅适用于整数或可映射类型，时间复杂度可达 O(n)。
稳定排序 vs 非稳定排序
- 稳定排序：相等元素的相对顺序在排序后保持不变。适用于多关键字排序场景（如先按分数排，再按姓名排）。
- 非稳定排序：相等元素的相对顺序可能改变。适用于仅需关注主关键字的场景。
内部排序 vs 外部排序
- 内部排序：数据完全加载到内存中处理，速度快。
- 外部排序：数据量超过内存容量，需借助外存（硬盘），通过分块归并完成。
插入排序
直接插入排序
思想：将未排序元素逐个插入到已排序部分的正确位置，类似整理扑克牌。
实现：
void InsertSort(int* a, int n) {
for (int i = 0; i <= n - 2; i++) {
int end = i;
int tmp = a[end + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
属性：
- 时间复杂度：最坏 O(n²)，最好 O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
- 适用：小规模数据、基本有序数据
希尔排序
思想：插入排序的改进版。通过分组插入，优先处理距离较远的元素，减少移动次数。
实现：
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
for (int i = 0; i <= n - gap - 1; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
} else {
break;
}
}
a[end + gap] = tmp;
}
}
}
属性：
- 时间复杂度：取决于增量序列，Knuth 增量约为 O(n^1.3)
- 空间复杂度：O(1)
- 稳定性：不稳定
选择排序
简单选择排序
思想：每次从未排序部分选出最小元素，放到已排序末尾。
实现：
void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
while (begin < end) {
int minn = begin, maxx = begin;
for (int i = begin + 1; i <= end; i++) {
if (a[i] < a[minn]) minn = i;
if (a[i] > a[maxx]) maxx = i;
}
Swap(&a[minn], &a[begin]);
if (maxx == begin) maxx = minn;
Swap(&a[maxx], &a[end]);
begin++; end--;
}
}
void Swap(int* a, int* b) {
int tmp = *a; *a = *b; *b = tmp;
}
属性：
- 时间复杂度：始终 O(n²)
- 空间复杂度：O(1)
- 稳定性：不稳定
堆排序
思想：利用堆结构（完全二叉树）高效选择最大/最小值。
实现：
void AdjustDown(int* a, int parent, int n) {
int maxChild = (parent << 1) + 1;
while (maxChild < n) {
if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {
maxChild += 1;
}
if (a[parent] >= a[maxChild]) return;
Swap(&a[parent], &a[maxChild]);
parent = maxChild;
maxChild = (parent << 1) + 1;
}
}
void HeapSort(int* a, int n) {
for (int i = (n - 1 - 1) >> 1; i >= 0; i--) {
AdjustDown(a, i, n);
}
int end = n - 1;
while (end > 0) {
Swap(&a[0], &a[end]);
end--;
AdjustDown(a, 0, end + 1);
}
}
属性：
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 稳定性：不稳定
交换排序
冒泡排序
思想：重复比较相邻元素，将较大元素逐步'冒泡'到末尾。
实现：
void BubbleSort(int* a, int n) {
for (int i = 1; i <= n - 1; i++) {
int flag = 1;
for (int j = 1; j <= n - i; j++) {
if (a[j - 1] > a[j]) {
Swap(&a[j - 1], &a[j]);
flag = 0;
}
}
if (flag) break;
}
}
属性：
- 时间复杂度：最坏 O(n²)，最好 O(n)
- 稳定性：稳定
快速排序
思想：分治法。选基准值将数组分为两部分，递归排序。
分区策略：
- Hoare 对撞指针：左右指针向中间扫描，相遇处放基准。
- Lomuto 快慢指针：快指针遍历，慢指针标记小于基准区边界。
- 挖坑法：填坑挖坑，最后填入基准。
实现（递归）：
int PartSort3(int* a, int left, int right) {
int mid = GetMid(a, left, right);
Swap(&a[left], &a[mid]);
int key = a[left];
int hole = left;
int begin = left, end = right;
while (begin < end) {
while (begin < end && a[end] >= key) end--;
a[hole] = a[end]; hole = end;
while (begin < end && a[begin] <= key) begin++;
a[hole] = a[begin]; hole = begin;
}
a[hole] = key;
return hole;
}
void QuickSort(int* a, int left, int right) {
if (left >= right) return;
int key = PartSort3(a, left, right);
QuickSort(a, left, key - 1);
QuickSort(a, key + 1, right);
}
非递归实现：使用栈模拟递归调用过程，避免栈溢出风险。
属性：
- 时间复杂度：平均 O(n log n)，最坏 O(n²)
- 空间复杂度：O(log n)
- 稳定性：不稳定
归并排序
思想：分治法。将数组不断分割直到长度为 1，然后合并有序子数组。
实现（递归）：
void _MergeSort(int* a, int* tmp, int begin, int end) {
if (begin >= end) return;
int mid = begin + ((end - begin) >> 1);
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int pos = begin;
while (begin1 <= end1 && begin2 <= end2) {
if (a[begin1] <= a[begin2]) tmp[pos++] = a[begin1++];
else tmp[pos++] = a[begin2++];
}
while (begin1 <= end1) tmp[pos++] = a[begin1++];
while (begin2 <= end2) tmp[pos++] = a[begin2++];
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n) {
int* tmp = (int*)malloc(n * sizeof(int));
if (!tmp) { perror("malloc fail"); return; }
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
属性：
- 时间复杂度：始终 O(n log n)
- 空间复杂度：O(n)
- 稳定性：稳定
计数排序
思想：非比较排序。统计每个元素出现次数，按计数顺序输出。
实现：
void CountSort(int* a, int n) {
int minn = a[0], maxx = a[0];
for (int i = 0; i < n; i++) {
if (a[i] < minn) minn = a[i];
if (a[i] > maxx) maxx = a[i];
}
int range = maxx - minn + 1;
int* count = (int*)calloc(range, sizeof(int));
if (!count) { perror("calloc fail"); return; }
for (int i = 0; i < n; i++) count[a[i] - minn]++;
int pos = 0;
for (int i = 0; i < range; i++) {
while (count[i]--) a[pos++] = i + minn;
}
free(count);
}
属性：
- 时间复杂度：O(n + k)
- 空间复杂度：O(n + k)
- 稳定性：稳定
性能总结
| 排序算法 | 时间复杂度 (平均) | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 直接插入 | O(n²) | O(1) | 稳定 | 小规模、基本有序 |
| 希尔 | O(n^1.3) | O(1) | 不稳定 | 中等规模 |
| 简单选择 | O(n²) | O(1) | 不稳定 | 小规模 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 大规模、空间受限 |
| 冒泡 | O(n²) | O(1) | 稳定 | 教学、小规模 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 通用、大规模 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 大规模、链表 |
| 计数排序 | O(n + k) | O(n + k) | 稳定 | 范围有限整数 |
注意：实际应用中需根据数据特征（规模、分布、稳定性要求）选择合适的算法。