1. 排序概念及运用
排序，简单来说就是让一串记录按照某个关键字的大小，递增或递减地排列起来。这在数据处理中非常常见。
常见的排序算法主要包括插入、选择、交换、归并以及非比较排序等几大类。
![排序算法分类示意图]
2. 实现常见排序算法
2.1 插入排序
直接插入排序的思想很直观：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中。实际生活中玩扑克牌理牌时，用的就是这个逻辑。
2.1.1 直接插入排序
当插入第 i 个元素时，前面的 arr[0]...arr[i-1] 已经排好序，此时用 arr[i] 与前面的元素顺序比较，找到插入位置，将 array[i] 插入，原来位置上的元素顺序后移。
void InsertSort(int* arr, int n) {
// i 表示有序数组的最后一个值
// arr[n-1] 后面没有待排序的数，所以 i < n-1
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²)（最差情况），最好情况 O(n)。
- 空间复杂度：O(1)。
2.1.2 希尔排序
希尔排序又称缩小增量法。它是在直接插入排序基础上的改进。基本思想是：先选定一个整数 gap，把待排序文件所有记录分成各组，对每一组内的记录进行排序，然后 gap 缩小，再分组排序，直到 gap=1 时，相当于直接插入排序。
void ShellSort(int* arr, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1; // +1 是因为当 gap=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;
}
}
}
注意 希尔排序的时间复杂度估算比较复杂，因为 gap 的取值很多，导致很难去精确计算。通常认为其优于直接插入排序，但具体性能取决于 gap 序列的选择。
2.2 选择排序
选择排序的基本思想是：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
2.2.1 直接选择排序
// 优化后版本
void SelectSort(int* arr, int n) {
int begin = 0, end = n - 1;
while (begin < end) {
int mini = begin, maxi = begin;
for (int i = begin + 1; i <= end; i++) {
if (arr[i] > arr[maxi]) {
maxi = i;
}
if (arr[i] < arr[mini]) {
mini = i;
}
}
if (begin == maxi) {
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
++begin;
--end;
}
}
特性总结
- 思考非常好理解，但是效率不是很好，实际中很少使用。
- 时间复杂度：O(N²)。
- 空间复杂度：O(1)。
2.2.2 堆排序
堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
2.3 交换排序
交换排序基本思想：根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
2.3.1 冒泡排序
冒泡排序是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。
void BubbleSort(int* arr, int n) {
int exchange = 0;
for (int i = 0; i < n - 1; 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²)。
- 空间复杂度：O(1)。
2.3.2 快速排序
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法。其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。
2.3.2.1 Hoare 版本
算法思路：创建左右指针，确定基准值。right 从右向左找出比基准值小的数据，left 从左向右找出比基准值大的数据，左右指针数据交换。
这里有个细节要注意：为什么跳出循环后 right 位置的值一定不大于 key？当 left > right 时，即 right 走到 left 的左侧，而 left 扫描过的数据均不大于 key，因此 right 此时指向的数据一定不大于 key。
int _QuickSort_Hoare(int* arr, int left, int right) {
int keyi = left;
left++;
while (left <= right) {
// right: 从右往左找小于基准值的
while (left <= right && arr[right] > arr[keyi]) {
--right;
}
// left: 从左往右找大于基准值的
while (left <= right && arr[left] < arr[keyi]) {
++left;
}
// 这里找到 left 比基准值大，right 比基准值小
if (left <= right)
Swap(&arr[left++], &arr[right--]);
}
// right 的位置就是基准值的位置
Swap(&arr[keyi], &arr[right]);
return right;
}
void QuickSort(int* arr, int left, int right) {
if (left >= right) {
return;
}
int keyi = _QuickSort_Hoare(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
注意 如果基准值找得不好或者数组本身有序，时间复杂度可能退化为 n²。
2.3.2.2 挖坑法
思路：创建左右指针。首先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的'坑'，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，结束循环后将最开始存储的分界值放入当前的'坑'中。
int _QuickSort_Pit(int* arr, int left, int right) {
int hole = left;
int key = arr[hole];
while (left < right) {
while (left < right && arr[right] > key) {
--right;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key) {
++left;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
2.3.2.3 Lomuto 前后指针
创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。
int _QuickSort_Lomuto(int* arr, int left, int right) {
int prev = left, cur = left + 1;
int key = left;
while (cur <= right) {
if (arr[cur] < arr[key] && ++prev != cur) {
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
Swap(&arr[key], &arr[prev]);
return prev;
}
特性总结
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(logn)。
2.3.2.4 非递归版本
非递归版本的快速排序需要借助栈结构来实现。
void QuickSortNonR(int* arr, int left, int right) {
ST st;
STInit(&st);
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st)) {
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
// 单趟
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end) {
if (arr[cur] < arr[keyi] && ++prev != cur)
Swap(&arr[prev], &arr[cur]);
++cur;
}
Swap(&arr[keyi], &arr[prev]);
keyi = prev;
// [begin, keyi-1] keyi [keyi+1, end]
if (keyi + 1 < end) {
STPush(&st, end);
STPush(&st, keyi + 1);
}
if (begin < keyi - 1) {
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}
2.4 归并排序
归并排序建立在归并操作上，采用分治法。将已有序的的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
void _MergeSort(int* arr, int left, int right, int* tmp) {
if (left >= right) {
return;
}
int mid = (right + left) / 2;
// [left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;
// 合并两个有序数组为一个数组
while (begin1 <= end1 && begin2 <= end2) {
if (arr[begin1] < arr[begin2]) {
tmp[index++] = arr[begin1++];
} else {
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1) {
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2) {
tmp[index++] = arr[begin2++];
}
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n) {
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n - 1, tmp);
free(tmp);
}
特性总结
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(n)。
2.5 非比较排序
2.5.1 计数排序
计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。
操作步骤：
- 统计相同元素出现次数。
- 根据统计的结果将序列回收到原来的序列中。
void CountSort(int* arr, int n) {
// 找 min，max
int min = arr[0], max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}
// 确定数组大小 range
int range = max - min + 1;
int* count = (int*)malloc(sizeof(int) * range);
if (count == NULL) {
perror("malloc fail");
exit(1);
}
// 对 count 初始化
memset(count, 0, sizeof(int) * range);
// 统计次数
// 通过映射的方式将数组保存在 count 数组中
// 映射的方式 == 原数组的值 - min
for (int i = 0; i < n; i++) {
count[arr[i] - min]++;
}
// 将 count 数组中的数据还原到 arr 数组中
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i]--) {
arr[index++] = i + min;
}
}
free(count);
}
特性总结
- 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
- 时间复杂度：O(n + range)。
- 空间复杂度：O(range)。
- 稳定性：稳定。
3. 辅助工具函数
为了支持上述算法，我们需要一些基础的工具函数，比如交换和简单的栈实现。
void Swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
// 简单的栈结构定义
typedef int STDataType;
typedef struct Stack {
STDataType* arr;
int top;
int capacity;
} ST;
void STInit(ST* ps) {
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void STDestroy(ST* ps) {
if (ps->arr) free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x) {
assert(ps);
if (ps->top == ps->capacity) {
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL) {
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top++] = x;
}
void STPop(ST* ps) {
assert(!STEmpty(ps));
ps->top--;
}
bool STEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
4. 排序算法复杂度及稳定性分析
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(n log n) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 稳定 |
在实际开发中，我们通常会根据数据规模、内存限制以及对稳定性的要求来选择合适的排序算法。例如，对于小规模数据，插入排序往往表现不错；而对于大规模随机数据，快速排序通常是首选。
