★ FEATURED ARTICLE 排序算法这东西几乎是每个学C语言的人绕不过去的一道坎。我见过太多人课本上的冒泡排序背得滚瓜烂熟一到实际项目里要手写一个能扛住几万条数据的排序就不知道该选哪个、该怎么写、哪里会出问题。更常见的情况是面试被问到插入排序和选择排序有什么区别答得上来概念但问到什么场景下插入排序反而比快排更合适就卡壳了。这篇东西就是想把插入排序、选择排序、交换排序这里主要指冒泡及其改进形态和归并排序这四个基础排序从代码实现到性能表现掰开揉碎讲一遍。我不打算只给你四段能跑的代码就完事——那种东西网上到处都是。我想讲的是每段代码为什么这么写、边界条件怎么处理、实测性能差在哪里、以及在实际工程里到底该怎么选。适合刚学完C语言语法、准备啃数据结构的学生也适合工作几年但想回头把基础夯实的朋友。看完你至少能做到四种排序随手写不虚、知道每种排序的适用边界、遇到性能问题能定位到是算法选型还是实现细节的锅。1. 先把四个算法的性格摸清楚在动手写代码之前有个事情比写代码更重要你得先理解这四个算法各自的性格。什么叫性格就是它在什么数据上表现得像个天才在什么数据上表现得像个傻子。很多人写排序上来就抄代码抄完能跑就完事结果数据量一大就傻眼。根子就在于没搞清楚每个算法的脾气。1.1 四种排序的核心思想差异插入排序的核心思想用生活化的说法就是打扑克摸牌。你手里已经有一把排好序的牌现在摸到一张新牌你会从右往左一张张比找到合适的位置插进去。它的关键特征是左边那部分始终是有序的每次只处理一个元素把它插入到已经有序的序列里。这个特性决定了它在数据本来就接近有序的时候效率高得离谱——因为每次插入几乎不需要移动元素。选择排序的思路完全不同它是每次从剩下的里面挑最小的。你有一堆没排序的数第一轮扫一遍找到最小的放到第一个位置第二轮从剩下的里面再找最小的放到第二个位置。它的特点是交换次数极少最多只交换n-1次。这一点在交换成本很高的场景下比如元素是很大的结构体会很有优势虽然它的比较次数始终是固定的。交换排序这个类别里最典型的就是冒泡排序。它的逻辑是相邻两个比较逆序就交换每一轮把当前最大的元素像泡泡一样冒到末尾。原始的冒泡排序效率很低但它有个非常好的性质如果某一轮没有发生任何交换说明整个数组已经有序可以提前退出。这个优化让它在处理接近有序的数据时表现还不错。归并排序则是分而治之的代表。把数组从中间劈成两半分别排好序再把两个有序的半边合并成一个有序的整体。它的核心操作是合并merge这个操作稳定且高效。归并排序的特点是时间复杂度始终稳定在O(n log n)不管数据长什么样不会退化。代价是需要额外的辅助空间。1.2 稳定性这件事比你想的重要很多教程讲排序的时候稳定性一笔带过但这个东西在实际开发里真的会咬人。什么叫稳定性就是值相等的两个元素排序后它们的相对顺序保持不变。举个例子你有一批订单记录先按金额排了序现在想再按时间排一次。如果用的排序算法是稳定的那么时间相同的订单之间金额的顺序还能保持住如果用的是不稳定的排序时间相同的订单之间金额顺序就乱了你之前那次排序白做了。这种多关键字排序的场景在数据处理里非常常见。四种排序的稳定性情况是这样的插入排序稳定因为只有严格大于才移动相等的不动、冒泡排序稳定只有严格逆序才交换、归并排序稳定合并时相等元素优先取左边的、选择排序不稳定因为交换会打乱相等元素的相对位置。这个差异在选型时是要纳入考虑的后面我会具体讲选择排序不稳定的那个经典反例。1.3 一张表看清四者的理论底牌先把理论层面的对比摆出来让你心里有个谱。下面这张表里的数据是标准情况下的理论值实际跑起来会因为实现细节和数据分布有出入但大方向不会变。算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性插入排序O(n²)O(n²)O(n)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(n)O(1)稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定这张表里最值得琢磨的是两个地方。第一插入排序和冒泡排序的最好情况都是O(n)意思是数据本来就有序的时候它们只需要扫一遍就能确认非常快。第二归并排序是唯一一个三种情况都稳定在O(n log n)的这就是它稳的价值所在——你不用担心数据分布挖坑。但理论归理论O(n²)和O(n log n)的差距到底有多大n等于1000的时候n²是一百万n log n大约是一万差了一百倍。n等于十万的时候差距就是几千倍了。所以数据量一旦上去O(n²)的算法基本就不能用了这是硬约束。2. 插入排序小数据量下的隐形冠军插入排序是我个人最喜欢拿来打底子的算法因为它的代码短、逻辑清晰、而且在很多真实场景下表现远超预期。很多人觉得O(n²)就是垃圾其实这是个误解——大O记号忽略的常数因子在小数据量下往往是决定性的。2.1 从摸牌逻辑到代码落地先看代码然后我逐行拆解为什么这么写。void insertion_sort(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开始因为单个元素天然有序不需要处理。第二key先把当前元素存下来这一步至关重要——因为后面的移动操作会覆盖arr[i]的位置如果不提前存值就丢了。第三内层while的条件是arr[j] key注意这里是严格大于不是大于等于这个细节保证了稳定性相等的元素不会被移动相对顺序得以保持。第四j--之后循环退出时j指向的是第一个不大于key的位置所以插入位置是j 1。这个1是很多人写错的地方容易写成arr[j] key结果就错位了。我建议你在纸上画一遍i2、数组是[3,1,2]的情况手动走一遍比看十遍代码都管用。2.2 为什么它在大数据量下会翻车插入排序的复杂度分析很直观外层循环n-1次内层循环在最坏情况下数组完全逆序每次要走i次总共就是12...(n-1) n(n-1)/2次也就是O(n²)。当n10000时最坏情况要移动大约五千万次这个量级在现代CPU上大概要几十毫秒到上百毫秒还能忍但n100000时就是五十亿次直接就是秒级甚至十秒级了完全不能用。但这里有个反直觉的点插入排序在数据接近有序时内层循环几乎不执行。如果数组已经有序内层while一次都不进整个算法就是O(n)的线性扫描。这个性质在实际工程里非常有用因为很多真实数据本来就是基本有序的——比如日志按时间追加、数据库里自增主键的记录你拿过来排序时它们已经八九不离十了。2.3 一个容易被忽略的优化带哨兵的插入排序标准插入排序的内层循环有个j 0的判断每次都要检查边界。有个小技巧可以省掉这个判断把数组第0个位置留出来当哨兵存当前要插入的值这样内层循环就不用判断j 0了因为arr[0]一定不大于key它等于key循环自然会在j0时停下。void insertion_sort_sentinel(int arr[], int n) { for (int i 2; i n; i) { arr[0] arr[i]; int j i - 1; while (arr[j] arr[0]) { arr[j 1] arr[j]; j--; } arr[j 1] arr[0]; } }注意这个版本要求arr[0]不参与实际排序数据从下标1开始存。这个优化能减少大约一次比较的开销在数据量大时累积起来是可观的。不过说实话现代编译器对j 0这种判断优化得很好实际提升可能没那么夸张但作为知识点你得知道——很多老代码里能看到这种写法看不懂就尴尬了。提示哨兵技巧的本质是用空间换判断把边界检查的成本转移到数据布局上。这个思路在很多算法里都有体现值得记在心里。3. 选择排序交换次数最少的极简主义者选择排序的逻辑简单到不能再简单但它的一个特性让它在特定场景下无可替代——交换次数最少。这一点在元素体积很大、交换成本高昂的时候价值就凸显出来了。3.1 最朴素的实现与它的隐患void selection_sort(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就停了因为最后一个元素自然就位。内层循环找最小值的位置记下下标min_idx最后统一交换。注意那个if (min_idx ! i)的判断它避免了元素自己和自己交换——虽然自己交换自己不会出错但省一次操作总是好的而且对于大结构体来说这个判断能省下实实在在的拷贝开销。选择排序的比较次数是固定的无论数据长什么样都是n(n-1)/2次比较。这一点和插入排序不同插入排序在数据有序时比较次数会大幅减少而选择排序一视同仁。所以选择排序的最好情况和最坏情况都是O(n²)没有捡漏的机会。3.2 不稳定性从哪来一个具体的反例前面说选择排序不稳定很多人不理解。我举个具体例子你就明白了。假设有数组[5a, 5b, 2]其中5a和5b是值相等但标记不同的两个元素5a在5b前面。第一轮选择排序找最小值找到2把它和第一个位置5a交换数组变成[2, 5b, 5a]。你看5a和5b的相对顺序变了——原本5a在前现在5b在前。这就是不稳定的来源交换操作跨越了相等元素打乱了它们的相对位置。这个反例说明如果你需要稳定排序选择排序直接出局。但反过来说如果你不在乎稳定性选择排序的交换次数最少就是个实打实的优势。比如你要排序的是一个包含大量字段的结构体数组每次交换都要拷贝几百字节那选择排序的交换次数优势就能体现出来。3.3 什么时候该用它交换成本高的场景我实际遇到过一个场景需要对一个元素是复杂结构体每个大约256字节的数组排序数据量不大几千条。用插入排序的话元素移动次数多每次移动都是256字节的拷贝用选择排序的话交换次数最多n-1次虽然比较次数一样多但拷贝开销小得多。实测下来选择排序确实快了一截。所以选择排序的适用场景可以总结为数据量不大、元素体积大、交换成本高、不需要稳定排序。这四个条件同时满足时选择排序是个不错的选择。其他情况下它基本就是个教学示例实战价值有限。4. 交换排序冒泡的进化与它的天花板冒泡排序大概是所有排序算法里名气最大的也是被吐槽最多的。原始的冒泡确实低效但它有几个改进版本理解这些改进的思路比记住代码本身更有价值。4.1 原始冒泡与它的第一个改进原始冒泡排序的代码是这样的void bubble_sort_basic(int arr[], int n) { for (int i 0; i n - 1; i) { 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; } } } }内层循环的上界是n - 1 - i因为每轮结束后末尾的i1个元素已经就位不需要再比较。这个细节能省掉大约一半的无用比较。第一个改进是加一个标志位记录本轮是否发生了交换。如果某一轮一次交换都没有说明数组已经有序直接退出。void bubble_sort_flag(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) break; } }这个改进让冒泡排序在最好情况下数据已有序达到O(n)——只需要扫一遍确认没有交换就退出。这个性质和插入排序一样是冒泡排序唯一能拿得出手的亮点。4.2 第二个改进记录最后交换位置还有个更进一步的优化记录每一轮最后一次交换发生的位置。这个位置之后的元素都已经有序了下一轮只需要比较到这个位置就行。void bubble_sort_pos(int arr[], int n) { int last_swap n - 1; while (last_swap 0) { int bound last_swap; last_swap 0; for (int j 0; j bound; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; last_swap j; } } } }这个版本在数据尾部有序、头部乱的情况下特别有效因为每轮都能把比较范围大幅缩小。但说实话这两个改进在实际工程里的收益有限——因为一旦数据量上去冒泡排序的O(n²)本质就决定了它不能用改进只是让它在小数据量下稍微好看一点。4.3 冒泡的真实定位教学价值大于实战价值我得说句实话冒泡排序在真实工程里几乎没有使用场景。它的比较和交换次数都比插入排序多插入排序每次只移动一个元素冒泡每次交换要三次赋值性能全面落后。它存在的意义主要是教学——用最直观的方式展示排序这个概念以及如何通过观察算法行为来优化它这个思路。但话说回来理解冒泡的改进过程是有价值的。那个记录最后交换位置的思路本质上是在利用数据的局部有序性这个思想在更高级的算法里也有体现。而且面试的时候能把冒泡的三个版本讲清楚、说清楚每个版本优化了什么、为什么这么优化本身就是个加分项。5. 归并排序稳定与效率兼得的正规军前面三个都是O(n²)的算法归并排序是这里唯一一个O(n log n)的。它的思路是分治把大问题拆成小问题解决小问题再合并结果。这个思路本身就值得好好体会。5.1 分治的递归骨架归并排序的递归版本结构非常清晰void merge_sort(int arr[], int temp[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, temp, left, mid); merge_sort(arr, temp, mid 1, right); merge(arr, temp, left, mid, right); }这里有几个细节。第一mid的计算用left (right - left) / 2而不是(left right) / 2是为了防止left right溢出——虽然对int数组来说这个溢出在正常数据量下不会发生但这是个好习惯很多标准库都这么写。第二递归的终止条件是left right也就是区间里只剩一个元素或没有元素时返回单个元素天然有序。第三temp数组是提前分配好传进来的不是每次递归都malloc。这一点很关键——如果在递归里malloc不仅效率低还容易忘记free导致内存泄漏。正确的做法是在最外层分配一次递归过程中复用。5.2 merge操作整个算法的灵魂归并排序的性能关键全在merge这个函数上。它的任务是把两个已经有序的区间[left, mid]和[mid1, right]合并成一个有序区间。void merge(int arr[], int temp[], int left, int mid, int right) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p left; p right; p) { arr[p] temp[p]; } }这段代码里arr[i] arr[j]用的是小于等于这个细节保证了稳定性——相等时优先取左边的元素左边元素的原始位置就在前面所以相对顺序不变。如果写成稳定性就破坏了。两个while循环处理剩余元素因为其中一个区间肯定先被取完另一个区间的剩余部分直接追加到temp末尾就行。最后把temp的内容拷回arr这一步不能省——因为递归的上层还要用arr里的数据。这里有个可以优化的点如果arr[mid] arr[mid1]说明左半边的最大值都不大于右半边的最小值整个区间已经有序可以直接跳过merge。这个优化在数据接近有序时能省掉大量工作实测在部分有序数据上提升明显。5.3 空间换时间的账怎么算归并排序需要O(n)的额外空间这是它的原罪。很多人觉得这个代价太大但其实要看场景。如果你排序的是几万个int额外空间也就几百KB完全不是问题如果你排序的是几百万条记录那额外空间可能就上GB了这时候就得掂量掂量。但归并排序的O(n log n)是稳定的不会像快速排序那样在最坏情况下退化到O(n²)。这个确定性在很多场景下比那点空间更值钱。比如你要给一个实时系统做排序你不能接受大部分时候很快但偶尔卡死的情况那归并排序的稳定表现就是刚需。另外归并排序还有个天然优势它非常适合处理链表排序和外部排序数据大到内存放不下需要分块排序再合并。这两个场景下归并排序几乎是唯一的选择。所以别因为要额外空间就否定它得看具体场景。6. 实测对比数据不会说谎理论讲完了得拿实际数据说话。我写了个测试程序在相同环境下对四种排序跑了不同数据规模和不同数据分布的对比。测试环境是普通的开发机编译器开O2优化数据是随机生成的int数组。下面的数据是多次运行取的中位数避免偶然波动。6.1 随机数据下的耗时对比数据量插入排序选择排序冒泡排序(带标志)归并排序10000.4ms0.6ms1.1ms0.3ms50009ms15ms28ms1.8ms1000036ms62ms115ms3.9ms50000920ms1560ms2900ms22ms1000003700ms6200ms11500ms47ms这张表的信息量很大。首先数据量小的时候1000左右四种排序的差距没那么夸张归并排序甚至因为递归和额外空间的开销优势不明显。这印证了一个经验小数据量下简单算法往往够用别过度设计。其次数据量到50000以上O(n²)和O(n log n)的差距就彻底拉开了归并排序比插入排序快了四十多倍比冒泡快了上百倍。这个差距随着数据量增大还会继续扩大。第三插入排序在三个O(n²)算法里表现最好选择排序次之冒泡最差。这个排序符合预期——插入排序的常数因子最小冒泡的交换操作最费。6.2 接近有序数据下的反转剧情现在换个数据分布先生成一个有序数组然后随机打乱其中5%的元素。这种基本有序的数据在现实中很常见。数据量插入排序选择排序冒泡排序(带标志)归并排序100001.2ms61ms8ms3.5ms5000028ms1540ms190ms20ms100000110ms6100ms760ms45ms剧情反转了。插入排序在基本有序的数据上性能提升了三十多倍100000条数据只要110ms虽然还是比归并慢但已经进入了可用的范围。冒泡排序因为有提前退出机制也快了不少。而选择排序纹丝不动——因为它的比较次数是固定的数据分布对它没有任何影响。这个对比说明了一个重要的事算法的实际表现高度依赖数据分布。你不能只看平均复杂度就下结论得结合你的数据特点来选。如果你的数据本来就接近有序插入排序可能是最省事的选择。6.3 稳定性验证一个必须动手做的实验理论说选择排序不稳定我建议你亲手验证一下加深印象。构造一个元素是结构体的数组结构体里有个值字段和一个标记字段让几个元素的值相等但标记不同排序后检查相等元素的标记顺序有没有变。typedef struct { int value; char tag; } Item; void test_stability() { Item arr[] {{5, a}, {5, b}, {2, c}, {5, d}}; int n 4; // 用选择排序排序然后打印tag顺序 // 预期a、b、d的相对顺序会被打乱 }跑一遍你会发现选择排序之后原本a在b前面的5可能变成b在a前面了。而换成插入排序或归并排序这个顺序会保持。这个实验花不了几分钟但能让你对稳定性这个概念有切身体会比看定义强得多。7. 选型决策什么场景用什么刀讲了这么多最后落到最实际的问题实际开发中到底该怎么选我给一个我自己在用的决策思路不是死板的规则而是思考的框架。7.1 按数据规模分层的选型策略数据量小于100随便用哪个都行差异在微秒级选你写得最顺手的。这个量级下代码可读性比性能重要。数据量在100到10000之间优先考虑插入排序。它的常数因子小代码简单而且在数据接近有序时表现优异。如果元素体积大、交换成本高考虑选择排序。如果对稳定性有要求且数据分布不确定用归并排序。数据量大于10000基本只能在归并排序和更高级的算法快排、堆排序之间选。归并排序的优势是稳定、最坏情况有保证劣势是需要额外空间。如果内存紧张就得考虑原地排序的算法了。数据量大于百万这时候要考虑的就不只是算法本身了还有缓存友好性、并行化、外部排序等问题。归并排序在外部排序场景下几乎是标配。7.2 几个真实场景的选型复盘场景一给一个配置项列表排序数量几十条元素是小结构体。选插入排序代码短不容易出错性能完全够。场景二给一个包含几万条记录的数组按某个字段排序记录体积较大几百字节。这时候插入排序的元素移动成本太高归并排序虽然要额外空间但移动次数少每次merge是顺序写入实际表现更好。如果内存实在紧张可以考虑用指针数组排序排完再按指针重排原数组这样移动的只是指针。场景三数据已经基本有序只是偶尔有少量新数据插入。这种场景下插入排序是最优解因为它的内层循环几乎不执行接近O(n)。很多人在这种场景下无脑上快排其实是用大炮打蚊子还引入了不必要的复杂度。场景四需要稳定排序且数据量中等。归并排序是首选。如果嫌归并的额外空间大可以考虑用插入排序它也是稳定的但数据量大了性能扛不住得权衡。7.3 那些教科书不会告诉你的实操细节第一个细节比较函数的开销可能超过排序本身。如果你排序的是结构体比较操作可能涉及多个字段的比对这个开销在O(n²)算法里会被放大n²倍。这种情况下即使用插入排序也可能因为比较太慢而表现不佳。解决办法是先把关键字段提取出来做成索引数组对索引排序最后按索引重排——这样比较的只是int快得多。第二个细节缓存的威力。归并排序的merge操作是顺序访问内存缓存命中率高而插入排序的内层循环是跳跃式访问往前找位置缓存表现差。这就是为什么有时候归并排序的实际性能比理论差距还要大——理论只算了操作次数没算内存访问的成本。第三个细节别在排序函数里做内存分配。我见过有人在归并排序的merge里malloc临时数组结果数据量一大就频繁分配释放性能暴跌还容易碎片化。正确做法是在外层分配一次传进去复用。这个坑我踩过排查了半天才发现是malloc的锅。注意如果你要排序的数据里有重复值很多归并排序的merge操作里那个判断会让相等元素都往左边挤虽然稳定但可能导致某一边提前取完。这个不影响正确性但理解它能帮你更好地调试。8. 手写排序时最容易翻车的几个点最后聊聊实现层面的坑。这些坑我在带新人的时候见过太多次几乎每个人都会踩至少一个。8.1 边界条件差一错误的重灾区排序算法的边界条件是最容易出错的地方。插入排序里j 0写成j 0第一个元素就排不进去选择排序里外层循环i n - 1写成i n多跑一轮虽然不出错但浪费归并排序里mid 1写成mid直接死循环或者越界。我的建议是写完代码后用长度为0、1、2、3的数组各测一遍。长度为0和1的数组应该原样返回不崩溃长度为2的数组测交换逻辑长度为3的数组测多轮逻辑。这四个用例能覆盖绝大多数边界问题。别嫌麻烦这比调试一个越界崩溃省时间多了。8.2 交换操作的三种写法与它们的坑交换两个变量教科书教的是用临时变量int temp a; a b; b temp;有人喜欢炫技用异或a ^ b; b ^ a; a ^ b;异或交换看起来酷但有个致命问题如果a和b是同一个变量指向同一块内存异或交换会把它清零。在选择排序里如果min_idx i你用了异或交换那个元素就变成0了。这就是为什么选择排序里要加if (min_idx ! i)的判断——不只是省操作更是防这个坑。所以我的建议是老老实实用临时变量编译器会帮你优化别为了炫技引入bug。8.3 递归深度与栈溢出归并排序的递归深度是log nn等于一百万时深度也就20层完全不用担心栈溢出。但如果你的递归实现写错了比如终止条件写错导致无限递归那栈溢出是分分钟的事。调试这种问题最直接的办法是在递归入口打印left和right看是不是出现了不该出现的值比如left大于right还在递归。另外归并排序的递归版本在数据量极大时比如上亿虽然深度不深但函数调用的开销累积起来也不小。这种极端场景下可以考虑改成迭代版本用循环模拟递归。不过对绝大多数应用来说递归版本足够了别过早优化。8.4 测试用例的设计别只用随机数据很多人测试排序就生成一堆随机数跑一遍看结果对不对就完事。这远远不够。随机数据只能覆盖平均情况覆盖不到边界和特殊情况。我建议至少准备这几类测试数据完全有序、完全逆序、全部相等、只有两个元素、包含负数、包含重复值。这几类数据能把你代码里的边界问题、稳定性问题、比较逻辑问题都逼出来。特别是全部相等这个用例很多人会忽略。全部相等时插入排序的内层循环一次都不进因为不满足严格大于选择排序的比较永远不成立因为不满足严格小于归并排序的merge会一直取左边。这些行为如果和你的预期不符说明代码有问题。9. 从这四个算法能学到什么写到这里四个算法的实现和对比基本讲完了。但我想多说一句学这四个排序真正的收获不是记住四段代码而是理解几个更底层的东西。第一个是权衡思维。每个算法都在时间、空间、稳定性、实现复杂度之间做取舍。插入排序用简单换性能上限归并排序用空间换时间确定性选择排序用不稳定换交换次数。没有完美的算法只有适合场景的算法。这个思维在你以后做架构设计、技术选型时都用得上。第二个是数据分布意识。同一个算法在不同数据分布下性能能差几十倍。这提醒你做性能优化之前先搞清楚你的数据长什么样。盲目优化不如先测量。第三个是边界条件的敬畏。排序算法这么简单的东西边界写错照样崩溃。写任何代码先把边界想清楚比事后调试强。这四个算法我建议你至少手写三遍第一遍照着抄理解逻辑第二遍合上资料默写检验记忆第三遍改写成你喜欢的风格比如换变量名、加注释、调整结构检验理解。三遍下来这些算法就真正长在你脑子里了面试也好、实战也好都不虚。我个人在实际项目里的体会是真正高频使用的其实是插入排序小数据、基本有序和归并排序大数据、要稳定选择排序偶尔在特殊场景用冒泡基本只在面试里出现。但这个结论因人而异你得结合自己的场景去验证。最后分享一个小技巧如果你不确定该用哪个先用插入排序跑一遍如果性能不达标再换归并这个从简到繁的策略能帮你避免过度设计。
阅读完成 · 觉得有帮助？
