★ FEATURED ARTICLE 如果计算机专业的学生有一个躲不开的“坎”排序算法绝对要排进前三。考试要考面试要问实际写代码查数据、做排行榜、合并有序列表时也绕不开它。更别提那些经典教材里动辄一两百行的递归分治实现第一次看能把人看懵。但只要你把这8种常见排序算法的原理、特点和适用场景真正吃透数据结构这门课的半壁江山基本就稳了面试手撕代码也不慌。这篇文章我会直接给你一套可以“抄作业”的完整笔记先讲清楚为什么所有教材都要费劲讲排序、以及稳定性和复杂度这两个绕不开的基础概念然后把8种常见算法逐个拆开结合代码和具体场景讲清楚每一步在干什么、为什么能生效最后放一张对比表帮你做选型再把我自己踩过的几个“坑”和调试技巧一并分享。适合正在复习数据结构期末考的学生、准备算法面试的求职者以及写业务代码时突然拿不准“这个场景该用哪个排序”的开发者。1. 排序算法为什么是数据结构的必修课1.1 排序的本质与学习误区很多人刚学排序时会觉得C语言里一个qsortPython里一个sort()Java里Collections.sort()现成的排序方法到处都是为什么还要浪费时间研究底层算法这个想法我在刚上大学时也有过直到有一次写一个实时榜单需求数据量不大但需要频繁插入新成绩并保持有序我才意识到直接调 API 虽然快但一旦涉及自定义对象的多字段排序、稳定性要求、内存受限等场景不了解底层逻辑的人连参数都调不明白。从数据结构角度看排序不仅仅是“把一组数排整齐”它更多是训练你对“时间复杂度、空间复杂度、稳定性、分治思想、堆结构、递归”这些核心概念的综合运用。你看快速排序用到了分治、归并排序用到了合并有序序列、堆排序用到了完全二叉树和堆调整这些都是数据结构课上最核心的知识点。所以教材里反复讲排序并不是为了让我们背代码而是用排序这个最直观的应用场景把前面学过的结构全部串起来。常见的误区有两个一是死记硬背代码背完就忘二是只关注时间复杂度忽略稳定性、空间占用和常数因子。比如快速排序平均时间确实是 O(n log n)但它最坏会退化到 O(n²)而堆排序虽然稳定在 O(n log n)但实际运行往往比快速排序慢因为缓存不友好。这种细节不靠实际跑数据、分析源码光背复杂度表是体会不到的。1.2 两个必须搞懂的基础概念稳定性与复杂度先说稳定性。我当年第一次听到“稳定的排序算法”时懵了很久排序结果还能不稳定其实这里的稳定指的是如果两个元素的关键字值相等排序后它们的相对位置是否保持不变。举个例子一个学生列表先按班级排好再按成绩排序如果成绩相同的同学原来的班级顺序依然能保留那么这个排序算法就是稳定的如果交换了就是不稳定的。为什么重要因为业务里经常有“按主属性排序后再按从属性排序”的需求稳定排序可以保证第二次排序不会打乱第一次的次序。再就是复杂度。排序里面涉及三个维度时间最好、平均、最坏以及空间复杂度。时间最好很容易理解但很多人容易忽略最坏情况比如快速排序在对已经有序的数组进排序且选首个元素为基准时会退化到 n 的平方。空间复杂度则指额外需要的辅助存储空间像归并排序需要 O(n) 的辅助数组而堆排序是原地排序只需要 O(1)。此外还有一个维度叫“比较次数和交换次数”在数据元素非常大、比较本身很昂贵比如比较两个结构体时这个维度甚至比时间复杂度更关键。这两个概念先放在这里后面的每一种算法我都会按照“稳定性——复杂度——是否原地——适用场景”这四条线展开这样你就能在对比中体会为什么有的算法虽然时间复杂度相同但实际用起来差别却那么大。2. 8种排序算法全景拆解为了好记我按“从易到难、从基础到进阶”把8种算法分成两个梯队简单排序插入排序、希尔排序、选择排序、冒泡排序和高级排序归并排序、快速排序、堆排序、基数排序。这里要特别说明教材里讲“8种常见排序”通常就是这几种其中基数排序属于非比较型排序思路和前面七个完全不同单独理解。2.1 直接插入排序扑克牌式的经典直接插入排序是我个人认为最贴近生活的排序。你玩扑克牌起牌的时候每摸一张新牌就会把它插到手中已经排好序的牌堆里对应的位置这个过程就是插入排序的活生生例子。算法思路很简单把待排序序列看成两部分左边是已经排好序的有序区右边是未排序的无序区。每次从无序区拿出第一个元素从右到左跟有序区里的元素逐个比较找到合适的位置插进去。等无序区全部取完整个序列就排好了。我用 C 风格伪代码写一下void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这里有几个细节值得注意。第一为什么从i 1开始因为第0个元素天然就是一个有序区只需要从第二个元素开始插入。第二为什么要从后往前比较因为这样可以边比较边把元素往后挪不用额外开一个数组。第三注意比较条件是arr[j] key如果用那相等元素会被插到后面就变成不稳定了——当然这里我们一般用保证稳定。复杂度上最好情况下原数组已经有序每一趟只需要比较一次时间复杂度是 O(n)最坏情况下完全逆序每一趟都要比较和移动 i 次总共是 O(n²)平均也是 O(n²)。空间复杂度 O(1)稳定。实际开发中插入排序特别适合“近乎有序”的小规模数据。比如一个在线排行榜每天只有少量新数据插入用插入排序每次维护的代价几乎接近线性实测下来比重新全量排序快一个数量级。2.2 希尔排序插入排序的进阶版希尔排序是插入排序的改进版它的出发点是插入排序在“基本有序”时效率非常高但如果数据杂乱无章每趟移动次数太多。希尔排序的做法是先让序列“宏观有序”再逐步缩小间隔最后用一次完整的插入排序收尾。核心概念是增量序列gap。比如取 gap n/2每次缩小一半直到 gap1。每一轮把所有相隔 gap 的元素视为一组对每组分别做插入排序。代码看起来有点像“分组插入排序”void shellSort(int arr[], int n) { for (int gap n / 2; gap 1; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }看懂这段代码有个窍门它就是插入排序的i-1/j--全部替换成了i-gap/j-gap其他逻辑一模一样。当 gap1时代码就回归成标准插入排序。希尔排序的时间复杂度比较难精确分析理论上取决于增量序列的选择常见取法 n/2 递减时平均大约在 O(n^1.3) 到 O(n^1.5) 之间。空间复杂度 O(1)不稳定。为什么不稳定因为在分组插入过程中相等元素可能被分到不同组导致相对位置改变。实践经验是希尔排序在中小规模数据几千到几万元素时表现亮眼代码也简单适合嵌入式等资源受限的场景。但如果你面对的是海量数据还是得考虑下面的高级算法。2.3 简单选择排序最直观也最不实用的排序选择排序的思路比插入排序更容易理解每一轮从未排序区间里找出最小的元素放到区间的最前端。就好像你在一堆考试卷子里每次都挑出分数最低的一份放到一边。代码长这样void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { int temp arr[i]; arr[i] arr[min_idx]; arr[min_idx] temp; } } }无论数据状况如何外层循环 n-1 次内层循环总次数固定是 n(n-1)/2所以最好、最坏、平均复杂度都是 O(n²)。此外它属于“原地排序”空间 O(1)。但不稳定因为第 i 轮找到的最小元素可能与后面出现的相同值交换打破相对顺序。我不推荐在实际业务里使用选择排序——它的比较次数太多只在数据规模极小且你完全不想写复杂逻辑时才会考虑。不过作为一种经典教学案例它展现了“每轮锁定一个位置”的贪心思想而且交换移动次数很少这让我们能理解“比较开销”与“移动开销”之间的权衡。2.4 冒泡排序面试最爱问细节的排序冒泡排序应该是大众认知度最高的排序算法了。它的原理就像气泡从水底往上浮每轮比较相邻两个元素如果顺序错误就交换一趟下来“最大”或“最小”的元素会冒泡到末端。当然冒泡也有一个最经典的优化就是加一个标志位void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped 1; } } if (swapped 0) break; } }为什么要j n-1-i因为每完成一轮末尾就会多一个已排好的元素这部分无需再比较。标志位swapped的作用是如果一轮里没有任何交换说明序列已经有序可以直接结束。这让最好情况下的时间复杂度降为 O(n)。复杂度上最坏和平均都是 O(n²)空间 O(1)稳定。冒泡排序最大的问题是太慢但它的交换操作适合链表这种无法随机访问的数据结构在数组场景下基本被插入排序取代。不过面试官非常喜欢考冒泡的优化、稳定性、和“每一轮之后最大值一定在末尾”这类细节所以还是值得认真掌握。2.5 快速排序最常用的高级排序没有之一快速排序是应用最广的排序算法。教科书上把它称作“划分交换排序”核心思想是分治选一个基准值pivot把数组分成两部分左边都比基准小右边都比基准大然后递归对左右两部分排序。快排最关键的环节是“分区partition”。我用最常见的单边循环版Lomuto写int partition(int arr[], int low, int high) { int pivot arr[high]; // 选末尾元素做基准 int i low; // i 左侧都是已确认小于等于pivot的元素 for (int j low; j high; j) { if (arr[j] pivot) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[high]); return i; } void quickSort(int arr[], int low, int high) { if (low high) { int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); } }分区过程其实是在维护一个“左区间的右边界指针 i”。当发现一个比基准小的元素就把它换到左边i 右移一位。循环结束后基准值回到 i 的位置这样基准左边都小于等于它右边都大于等于它。快排的平均时间复杂度是 O(n log n)但最坏情况是 O(n²)——当每次选的基准恰好是当前区间的最大或最小值分区极不平衡时会出现。解决办法包括随机选基准、取“三数取中”等优化手段。快排不是稳定的因为交换过程会打乱相等元素顺序空间复杂度主要来自递归栈平均 O(log n)最坏 O(n)。实际开发中绝大多数语言内置排序的底层就是快排或它的变体比如C语言的qsort、C的std::sort用到快排插入排序混合。我自己在实现排行榜分页查询时也手动写过快排它对随机数据的性能确实强但你需要留意数组中大量重复元素时传统单边分区会让复杂度退化。这时用“双指针双向扫描 三路分区”可以明显缓解。2.6 归并排序稳定高效的稳定排序代表归并排序是典型的“分治”算法把数组从中间分成两半分别排序然后把两个有序子序列合并成一个有序序列。核心操作是“合并”需要额外一个临时数组。合并过程很像两个有序链表串起来void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int* L malloc(n1 * sizeof(int)); int* R malloc(n2 * sizeof(int)); for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) arr[k] L[i]; else arr[k] R[j]; } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; free(L); free(R); } void mergeSort(int arr[], int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } }注意区间边界的写法标准教材喜欢用mid (leftright)/2我建议写成left (right-left)/2避免leftright溢出这是个面试官爱考的细节。归并排序的时间复杂度非常稳定最好、最坏、平均都是 O(n log n)同时它还是高级排序中少见的稳定算法。代价是空间复杂度 O(n)因为每次合并都需要临时数组。在内存足够且对稳定性有强要求的场景比如数据库外部排序、链表的排序归并排序是首选。另外归并排序特别适合外部排序当数据量大到无法全部加载进内存时可以把数据切成若干块分别排好序再用多路归并合并这个思想我在处理几GB的日志文件时用过非常实用。2.7 堆排序利用完全二叉树结构排序堆排序是我认为“明明思路清晰但代码最容易写崩”的排序。它借助的是完全二叉树中的“大顶堆”结构每个父节点的值都大于等于其子节点。排升序时先建一个大顶堆然后把堆顶最大元素换到数组末尾缩小堆的范围再对新的堆顶执行下沉操作反复直到堆只有一个元素。void heapify(int arr[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(int arr[], int n) { for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }为什么建堆要从i n/2 - 1开始因为数组下标从0开始最后一个非叶子节点的下标就是n/2 - 1。从它开始向上逐个执行堆化能保证每个子堆都满足堆性质。下沉操作要递归到左右孩子是因为交换后子树可能被破坏需要继续调整。堆排序时间复杂度是稳定的 O(n log n)空间 O(1)不稳定属于原地排序。它的最大优点是“不必做全排序”时非常好用比如要从一亿条数据里挑出前100个最大值用堆维护一个大小为100的小顶堆复杂度是 O(n log 100)比全排序快得多。我本人在做Top K排行榜时基本都用堆而不是先全排再截取。2.8 基数排序不比较也能排序前面六种算法都依赖“比较两个元素的关键字”基数排序则完全不同它按关键字的每一位进行分配和收集。比如排序三位整数先按个位放入桶0-9按桶顺序收集再按十位、百位重复。这里的桶其实就是计数数组也叫计数排序的推广。我写一个基于“最低位优先LSD”的简单实现用计数思想完成一趟分配收集void countingSortForDigit(int arr[], int n, int exp) { int output[n]; int count[10] {0}; for (int i 0; i n; i) { int digit (arr[i] / exp) % 10; count[digit]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } for (int i 0; i n; i) arr[i] output[i]; } void radixSort(int arr[], int n) { int max arr[0]; for (int i 1; i n; i) if (arr[i] max) max arr[i]; for (int exp 1; max / exp 0; exp * 10) { countingSortForDigit(arr, n, exp); } }倒数第二个循环为什么从n-1往前遍历这是为了保证“按当前位排序时的稳定性”也就是同一位数相同的元素保留上一轮排好的顺序。这是基数排序成立的关键。基数排序的时间复杂度是 O(d(nk))其中 d 是最大数的位数k 是进制十进制里是10。当 d 是常数时可以认为复杂度是线性的 O(n)空间复杂度 O(nk)。它是稳定排序。它最大的局限是只能处理整数或能转换成正整数的数据字符串可以通过ASCII码处理而且不适合数据取值范围极大但数量很少的场景否则多余的桶会造成空间浪费。3. 复杂度对比与场景选型3.1 一张表看懂八种排序我把这8种排序的核心指标整理成一张表放在这里反复对照着看比你零散记忆高效得多排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性是否原地直接插入排序O(n²)O(n²)O(1)稳定是希尔排序O(n^1.3~1.5)O(n²)O(1)不稳定是简单选择排序O(n²)O(n²)O(1)不稳定是冒泡排序O(n²)O(n²)O(1)稳定是快速排序O(n log n)O(n²)O(log n)不稳定是归并排序O(n log n)O(n log n)O(n)稳定否堆排序O(n log n)O(n log n)O(1)不稳定是基数排序O(d(nk))O(d(nk))O(nk)稳定否注意希尔排序的最坏时间复杂度其实是一个仍有一定争议的话题不同的增量序列会导致不同结果。表里写的是较常见的“gap 取一半递减”时的最坏情况。如果你是应试复习以教材给出的结论为准即可。3.2 实际开发中怎么选这是我的个人经验不一定等于教科书标准答案但很有参考价值数据量很小少于50个元素且你不想写复杂代码直接插入排序最香。它在近乎有序时甚至比快排还快代码也简单。数据量中等几千个元素内存有限希尔排序是个不错的折中方案不需要递归也不会占用太多栈空间。数据量很大默认选择快速排序。前提是没有大量重复数据和恶意构造的逆序数据。如果有用随机基准或三路快排。数据量很大但要求稳定归并排序。比如数据库排序或需要保留原始输入顺序的场景。需要不断从大量数据中找Top K堆排序的变体维护大小为K的堆复杂度最低。待排序数据都是整数范围相对集中且位数不多基数排序会比所有比较排序都快毕竟它是线性近似。还有一点值得说语言内置的排序函数通常都已经做过工程级优化比如 Python 的 TimSort本质是二分插入归并的混合Java 的Arrays.sort()对基本类型用双轴快排、对对象用 TimSortC 的std::sort是内省排序快排堆排混合。这些内置版比你自己手写的版本几乎总是更快所以日常开发优先调库。手写排序的价值在于理解和特殊场景下的定制。4. 排序算法常见问题与调试实录4.1 边界条件与索引越界快排最容易翻车的地方我见过太多人写快排时在递归边界上出问题。最常见的一种是递归出口只写if (low high) return;但要考虑当 low high 时怎么办也就是空区间的情况。如果你调用quickSort(arr, low, p-1)而p恰好等于low那p-1 low此时如果不加low high的兜底判断就死循环了。靠谱的做法是统一写if (low high) return;这样空区间和单元素区间都能安全退出。另外找mid时不要用(leftright)/2在数组长度很大时可能整数溢出推荐用left (right-left)/2。类似的技巧还有在归并排序申请临时数组时先看需要分配多大不要直接把整个数组复制一遍否则空间开销会翻倍。4.2 稳定性误区等号用错的连锁反应很多人写代码时不太注意等号对稳定性产生的影响。例如插入排序里条件如果写成arr[j] key那相等元素的原有顺序就会反转插入排序就“变质”为不稳定排序。在归并排序的合并循环里如果把L[i] R[j]写成则当两个元素相等时会优先取右序列的元素同样破坏稳定性。这里有一个实用的检查方法在测试用例里准备一组“带编号的相同值”数据比如[{val: 3, id: 1}, {val: 2, id: 2}, {val: 3, id: 3}]排序后检查相同值的 id 顺序是否保持原样。我自己的测试脚手架里永远有一个这种用例任何一次算法实现版本变动都会先跑一遍。4.3 性能优化的几个亲身教训第一个教训是不要在递归排序中频繁创建临时数组。很多新手在每一次归并排序的merge内部malloc和free开销大得离谱。我的优化方案是在归并排序外层创建一个统一长度的临时数组通过下标参数传递进去复用只分配一次实测能快四五倍。第二个教训是对基本有序的大数组不要直接上普通快排。有一次我处理一个“几乎排好序”的用户表用经典快排选末尾为基准结果递归深度直接逼近 N代码没崩但半天不出结果。后来改成三数取中秒变正常。所以如果你要手写快排至少要做“三数取中”或随机选基准这个优化花费极小却能让最坏情况几乎不出现。第三个教训是基数排序并不总是“更快”。它需要额外的 O(nk) 空间而且 k 和 d 变大以后内存访问不连续CPU 缓存命中率低。我用整数范围 0 到 100 万的 50 万条数据做过对比基数排序确实比快速排序快但把范围改成 0 到 10 亿基数排序的效率优势就明显缩小因为需要处理更多位数桶操作变多。所以“线性算法一定更快”是个伪命题具体得看数据特征。4.4 调试排序代码的小工具与技巧如果你手写排序后总报错先别急着人眼盯代码。我习惯用三步排查写一个isSorted(arr)校验函数排序后调用检查是否有前一个元素大于后一个元素。能立刻发现大部分错误。用随机小数组长度10到20含重复值做测试把排序前后的数组打出来人眼观察哪一刻顺序不对。我通常会写一个辅助函数在每轮交换后打印当前状态快速定位问题。再用“相同值元素带身份证号”的方式测试稳定性方法上一节已经说过。如果想验证性能可以在不同规模下跑基准测试从 1k、10k、100k 到 1M记录时间。注意要先用随机数据预热避免 JIT 或虚拟内存带来的扰动。我自己的一个小脚本里会给每种算法跑多次取中位数这样对比复杂度更有说服力。写在后面排序算法要怎么学才不白学我个人在实际操作中的体会是排序算法千万别平均用力地去背。先用一两周时间把插入排序、快速排序、归并排序和堆排序彻底吃透做到能独立、无报错地写出来然后再去理解选择、冒泡、希尔和基数排序这些概念性的东西。因为前四个几乎涵盖了“插入、分治、递归、堆”这些最核心的方法论理解了它们后面再学任何排序都会特别快。最后再分享一个小技巧你在学某个排序时顺手用这个排序去解一道算法题比如用归并排序求逆序对、用堆排序求数据流中的中位数一旦把排序思想用到了实际问题里它就不再是考试包袱而变成你工具箱里一件真正趁手的工具。这种“以用带学”的方式比我当年对着书抄十遍代码有效得多。
阅读完成 · 觉得有帮助？
