别再死记！彻底吃透经典排序算法
·
🚀 吃透 6 大经典排序算法｜一网打尽 原理 + 手写源码 + 优化 + 面试坑
🔥 零基础也能看懂 | 💻 全程可运行 C 代码 | ⚡ 复杂度一眼对比 | ❌ 避开 90% 新手误区
📚 目录（一键跳转）
一、全局复杂度速查表（秒杀面试）
二、冒泡排序
✨ 算法核心思想
相邻元素两两比较，逆序交换，大数逐渐“冒泡”到末尾。
🎯 执行流程简述
1.从头遍历数组，相邻两两对比
2.前大后小就交换
3.一轮结束，最大值沉到末尾
4.未排序区间缩一位，重复直到有序
💡 手写核心代码
void BubbleSort(int* a,int n)
{
//实现多趟
for (int j = 0; j < n - 1; j++)
{
int flag = 0;
//实现一趟
for (int i = 1; i < n-j; i++)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
🚩 优化方案
有序标记提前终止、双向冒泡
❌ 高频易错坑点
1.内层循环边界写错
2.忘记提前终止，效率过低
三、选择排序
✨ 算法核心思想
每轮从未排序区选出最小值，放到有序区末尾。
🎯 执行流程简述
划分有序/无序区间，遍历找最小值下标，一轮一次交换。
💡 手写核心代码
void SelectSort(int* a, int left,int right)
{
int begin = left, end = right;
while (begin < end)
{
int min = begin;
int max = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] < a[min])
{
min = i;
}
if (a[i] > a[max])
{
max = i;
}
}
Swap(&a[begin], &a[min]);
if (max == begin)
{
max = min;
}
Swap(&a[end], &a[max]);
begin++;
end--;
}
}
⚖️ 优缺点 & 稳定性
交换次数少，但不稳定。
🚩 优化方案
前面排最小，后面排最大同时进行
❌ 新手踩坑
- 多次无效交换
- 误以为稳定排序
四、插入排序
✨ 算法核心思想
模拟打牌，逐个把元素插入前面有序区间。
🎯 执行流程简述
默认第一个数有序，后续元素向前比较、后移、插入空位。
💡 手写核心代码
void InsertSort(int* a,int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = tmp;
}
}
📌 特性总结
- 元素越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
五、希尔排序
🧠 核心思想
先选定一个整数，把待排序数据分成该整数组，所有距离为该整数的数为一组，并对每一组排序。整数不断缩小，当整数为1时，数在这一组就排好了顺序。
💡 手写核心代码
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
// +1保证最后一个gap一定是1
// gap > 1时是预排序
// gap == 1时是插入排序
gap = gap / 3 + 1;
for (size_t i = 0; i < n - gap; ++i)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
📌 特性总结
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，当gap == 1时，数组就接近有序了，这样可以实现优化效果。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法有很多。
- 稳定性：不稳定。
六、快速排序「核心必考」
🧠 分治 + 分区思想
选基准，小靠左、大靠右，递归分治。
🎯 基准选择技巧
左右双指针、随机基准、三数取中。
💡 手写核心代码
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
// left midi right
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return right;
}
else
{
return left;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
// hoare
int PartSort1(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int begin = left, end = right;
while (begin < end)
{
// 右边找小
while (begin < end && a[end] >= a[keyi])
{
--end;
}
// 左边找大
while (begin < end && a[begin] <= a[keyi])
{
++begin;
}
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[begin]);
return begin;
}
// 前后指针
int PartSort2(int* a, int left, int right)
{
// 三数取中
int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = prev+1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
// 避免有序情况下，效率退化
// 1、随机选key
// 2、三数取中
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int keyi = PartSort1(a, left, right);
// [left, keyi-1] keyi [keyi+1, right]
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
#include"Stack.h"
void QuickSortNonR(int* a, 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 = PartSort2(a, begin, end);
// [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);
}
⚡ 性能瓶颈 & 优化
- 三数取中法选key
- 递归到小区间，可以考虑使用插入排序
七、归并排序「稳定最优」
🧩 分治 + 合并逻辑
先二分拆分到底，再两两有序合并。
🎯 执行步骤拆解
拆 → 分 → 合并 → 回填数组。
💡 手写核心代码
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;
int mid = (begin + end) / 2;
// 如果[begin, mid][mid+1, end]有序就可以进行归并了
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid+1, end);
// 归并
int begin1 = begin, end1 = mid;
int begin2 = mid+1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while(begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
memcpy(a+ begin, tmp+ begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
tmp = NULL;
}
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
// gap每组归并数据的数据个数
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
// [begin1, end1][begin2, end2]
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);
// 第二组都越界不存在，这一组就不需要归并
if (begin2 >= n)
break;
// 第二的组begin2没越界，end2越界了，需要修正一下，继续归并
if (end2 >= n)
end2 = n - 1;
int j = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[j++] = a[begin1++];
}
else
{
tmp[j++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[j++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[j++] = a[begin2++];
}
memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
}
printf("\n");
gap *= 2;
}
free(tmp);
tmp = NULL;
}
📌 特性总结
- 需要O(N)空间复杂度，归并排序思考更多的解决磁盘中的外排序问题
- 时间复杂度:O(N*logN)
- 空间复杂度:O(N)
- 稳定性：稳定
八、计数排序–非比较排序
✨ 算法核心思想
1.统计相同元素出现次数
2.根据统计结果将序列回收到原来的序列中
💡 手写核心代码
void CountSort(int* a, int n)
{
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;
//printf("%d\n", range);
int* count = (int*)calloc(range, sizeof(int));
if (count == NULL)
{
perror("calloc fail");
return;
}
// 统计次数
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
// 排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
a[j++] = i + min;
}
}
free(count);
}
📌 特性总结
- 计数排序在数据范围集中，效率很高，但是适用范围有限。
- 时间复杂度：O(MAX(N,范围))
- 空间复杂度：O(范围)
- 稳定性：稳定
九、堆排序
✨ 算法核心思想
先把数组数据建堆，然后一次取出堆顶数据与数组最后一个数据交换，再调整堆，循环。
💡 手写核心代码
void AdjustDown(int* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // 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 = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
// 向下调整建堆 O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// O(N*logN)
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
📌 特性总结
- 时间复杂度：最好/最坏/平均都是O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 缺点：缓存不友好（访问不连续）
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
22
0- 0
已为社区贡献1条内容
所有评论(0)