1. 排序算法整体框架先搞清楚这8种算法该怎么分类从大一第一次接触数据结构到现在我先后经历了期末突击、考研408复习、面试刷题、带新人做技术分享这几个阶段一个很明显的感受是排序算法不是靠背代码背出来的而是靠理解框架串起来的。市面上流传的“8种常见排序算法”看似很多翻来覆去其实就两大阵营比较类排序和非比较类排序。比较类排序的核心动作是两两比较元素的大小并根据比较结果调整顺序。冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序都属于这一类。它们的共同特点是适用范围广不管数据是整数、浮点数还是字符串只要定义了比较规则就能用。非比较类排序则以计数排序为代表还有基数排序和桶排序它们通过统计待排数据的分布信息来完成排序不依赖“比较”这个动作所以在特定条件下能达到线性时间复杂度。分类这一步不是用来应付考试名词的它直接决定了你选算法时的思考路径。比如面试官问你“给一批年龄数据排序”你要立刻想到值域很小的场景计数排序是O(n)如果问的是“将近乎有序的大数组排序”插入排序的优化特性就体现出来了。脑子里先有框架再往框架里装细节才不会被11个排序算法教材里还有基数排序和桶排序打成一团浆糊。为了后面讲得清楚先把几个核心概念钉死。稳定性指的是如果两个元素的值相等排序后它们的相对位置会不会改变。不改变则称这个算法是稳定排序否则是不稳定排序。这个性质在真实业务中很重要比如按成绩降序排列成绩相同的人还要保持原来的学号顺序那就必须选用稳定排序。原地排序则是指排序过程中只需要常数级别的额外空间不借助跟数据规模成正比的辅助数组。把这8种算法的关键指标整理成一张表比背十遍书都管用排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性是否原地冒泡排序O(n²)O(n²)O(1)稳定是选择排序O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(1)稳定是希尔排序O(n^1.3)O(n²)O(1)不稳定是归并排序O(n log n)O(n log n)O(n)稳定否快速排序O(n log n)O(n²)O(log n)不稳定是堆排序O(n log n)O(n log n)O(1)不稳定是计数排序O(n k)O(n k)O(k)稳定否这就是整篇文章的地图。后面的每一节都是围绕这张表展开的我会把每格指标背后的“为什么”讲透再配可以照抄的代码和避坑经验。2. 三种O(n²)基础排序冒泡、选择、插入的细节与优化2.1 冒泡排序从学生会排队到代码实现冒泡排序大概是很多人人生中写的第一个排序。它的思路用学生排队做操来形容最贴切从队伍最前面开始相邻两个人比较身高如果前面的比后面的高就交换位置这样一路比下去最高的同学就像气泡一样“冒”到了队伍末尾。下一轮再对剩余的人做同样操作第二高的又到了正确位置。重复n-1轮队列就排好了。写这段“会学生队”的代码并不难但真正的考点在优化和边界条件上void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { // 标志位如果本轮没有交换说明已经有序提前结束 int swapped 0; // 内层循环的范围是 [0, n-1-i)后面i个元素已经归位 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) { break; } } }第一轮比较n-1次第二轮比较n-2次最后一轮比较1次总比较次数就是等差数列求和约n²/2。交换次数取决于逆序对数量最坏时也是n²/2。加上标志位优化的意义在于当数据已经有序时第一轮跑完发现没有交换直接break时间复杂度退化成O(n)。这是考试中的一个常考默认点——问“优化后的冒泡排序在最好情况下的复杂度”答案是O(n)。冒泡排序的稳定性来自“相邻交换”这个动作本身当两个相邻元素的比较结果是相等时我们的判断条件是arr[j] arr[j1]等于不交换所以相等元素的相对顺序不会被破坏。此外还有一个比较冷门但面试偶尔出现的变体双向冒泡排序鸡尾酒排序一轮从左到右把最大元素送到末尾下一轮从右到左把最小元素送到开头。它比单向冒泡的轮次可能少一半但复杂度的数量级没有变化。知道有这么个东西就够了真上手写的机会很少。2.2 选择排序直观但有个隐蔽的坑选择排序的思路比冒泡更简单每一轮在剩余元素中挑出最小的把它放到当前轮次的起始位置。比如数组[5, 3, 1, 4, 2]第一轮找出全局最小值1和第一个位置5交换第二轮在[5, 3, 4, 2]中找出最小值2和第二个位置交换以此类推。void selectionSort(int arr[], int n) { for (int i 0; i n - 1; i) { int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { int tmp arr[i]; arr[i] arr[minIndex]; arr[minIndex] tmp; } } }这段实现里最关键的变量是minIndex很多新手喜欢交换arr[i]和arr[j]那是冒泡的做法一定要分清。选择排序的比较次数是固定的n(n-1)/2不管数据是否有序所以它的最好、最坏、平均时间复杂度都是O(n²)。它的隐蔽问题出在稳定性上。请看这个例子[5a, 3, 5b, 1]其中两个5用a和b区分相对顺序。第一轮找到最小值1把它跟下标0的5a交换数组变成[1, 3, 5b, 5a]。你看原本排在前面的5a现在跑到了5b后面稳定性被破坏。所以选择排序是不稳定排序这里在考试和面试中经常以判断题或填空题的形式出现。2.3 插入排序打扑克牌时的天然操作插入排序是我个人最偏爱的基础排序因为它的思想和人类行为高度一致你打扑克牌抓牌的时候会把新抓到的牌从后往前挨个比较找到合适的位置插进去而不是像冒泡那样一轮一轮硬换。void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; // 把比key大的元素都往后移一位 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序的最好情况发生在数组已经有序时内层while循环一次都不会执行复杂度O(n)。它处理“近乎有序的大数组”时性能往往胜过O(n log n)的快速排序因为快排的递归开销和划分代价在此时反而成了负担。这个特性被不少生产环境看中比如Java的Arrays.sort()在对小规模数据做排序时用的就是改进后的插入排序TimSort的思想。它的稳定性很好因为插入的位置在第一个“不大于key”的元素之后相等元素的相对位置不会变化。同时它也是原地排序空间复杂度O(1)和冒泡、选择一样是“内存极度紧张时还能用的排序”。到这里三种O(n²)算法可以做个临别总结冒泡适合教学但实际项目里写它会被同事嫌弃选择排序思路简单但不稳定插入排序虽然形式上朴素却因为对“基本有序数据”的友好性在真实工程里有一席之地。3. 进阶比较排序希尔、归并、快速、堆排序的原理与实现3.1 希尔排序让插入排序“跳着走”希尔排序是第一个突破O(n²)时间复杂度的排序算法它的核心思想非常朴素插入排序太慢是因为元素只能一步一步地挪到目标位置如果让元素先大步跳着排序缩小数组的“无序程度”最后再做一次普通插入排序总代价反而更小。具体做法是选一组递减的增量序列比如先隔5个元素分组组内做插入排序再隔3个最后隔1个。这里的“分组”不是把数组切成几段而是按步长把下标差为增量的元素看作一组。比如数组有10个元素增量取5时下标0、5是一组1、6是一组2、7是一组……每组内部执行插入排序。void shellSort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { // 下面就是一个按gap分组的插入排序 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从gap开始逐个往后遍历等于同时处理所有分组而不是先处理完第0组再处理第1组。从代码视角看它只是把标准插入排序里的j-1换成了j-gap其他什么都没变。理解了这一点希尔排序就再也不会写错。希尔排序的时间复杂度与增量序列有关用最常见的gap n/2、n/4、...时平均复杂度O(n^1.3)左右。空间复杂度O(1)但它是不稳定排序——分组交换会把相等元素的相对位置打乱。考试中有一道常见的辨析题希尔排序本质上还是插入排序的改进版不是另一种独立的排序思想。3.2 归并排序分治思想的最好样板归并排序是数据结构课程里“分治法”的标配例子。它的思路一句话可以概括把数组分成两半分别把左半和右半排好序再把两个有序数组合并成一个整体有序的数组。递归下去当子数组只有一个元素时它天然有序然后逐层向上合并最终整个数组有序。合并两个有序数组的过程是关键。你得额外开一个临时数组用双指针分别扫描左半和右半谁的当前元素更小谁就先进临时数组。这个“额外空间”导致归并排序的空间复杂度是O(n)这也是它唯一不满足“原地排序”的原因。void merge(int arr[], int left, int mid, int right, int tmp[]) { int i left, j mid 1, k left; while (i mid j right) { // 注意这里用 保证稳定性 if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) { tmp[k] arr[i]; } while (j right) { tmp[k] arr[j]; } // 合并结果拷回原数组 for (int p left; p right; p) { arr[p] tmp[p]; } } void mergeSort(int arr[], int left, int right, int tmp[]) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid, tmp); mergeSort(arr, mid 1, right, tmp); merge(arr, left, mid, right, tmp); }稳定性是归并排序最值得炫耀的优点因为合并时arr[i] arr[j]的判断保证了相等元素中左边的先进临时数组相对顺序不变。它的时间复杂度是严格的O(n log n)不管数据初始状态如何都稳定在这个界上这是它比快速排序“口碑好”的原因。代价是需要一份跟原数组等长的辅助空间。如果面试中问到“外部排序怎么做”答案也和归并有关把大文件切成多个能载入内存的小块分别排序后做多路归并。这是归并排序在生产环境最重要的应用场景。3.3 快速排序性能王者但有三道坎快速排序是实际工程中用得最多的排序算法平均性能最优。核心思想也源于分治选一个基准值pivot把数组划分成“小于等于基准的左区域”和“大于等于基准的右区域”然后递归排序两个区域。难点不在分治框架而在“原地划分”怎么写。教材里经典的划分是Lomuto方案用数组最后一个元素做基准维护一个边界指针i凡是比基准小的都交换到前面去。另一种更高效的Hoare方案用两端指针向中间扫代码长一点但交换次数更少。我强烈建议你彻底吃透一种另一种至少能看懂int partition(int arr[], int low, int high) { // Lomuto划分法选最后一个元素作为pivot int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; } } int tmp arr[i]; arr[i] arr[high]; arr[high] tmp; return i; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }快速排序想在实际中发挥出O(n log n)的平均水平必须解决三道坎第一道是基准选择。如果数组本来就是有序的而你每次都选最后一个元素当基准那每次划分只消掉一个元素递归深度变成n时间复杂度退化到O(n²)。规避办法是“三数取中”在头、中、尾三个元素里选中间值当基准对近乎有序的数据这招特别有效。第二道是递归深度。快排的平均递归深度是O(log n)这是它的“空间复杂度O(log n)”的含义实际上来自于递归调用栈。最坏情况下深度O(n)会占用大量栈空间甚至栈溢出。第三道是区间划分太窄。当子数组长度小于某个阈值比如10~16时递归调用partition的常系数开销已经超过了插入排序的直接操作代价。工程实现里通常会在小规模区间时改用插入排序收尾很多教科书不写这点但实际性能差距很明显。稳定性方面快排在交换过程中会把相等元素的位置互相穿插所以它是不稳定排序。3.4 堆排序借助完全二叉树但不用真建树堆排序总给人一种“明明听着很熟写起来却总差一步”的感觉。它的底层结构是二叉堆但出于性能考虑我们并不会真的创建一棵树而是把数组原地看成一颗完全二叉树下标i的左右孩子分别是2*i1和2*i2父节点是(i-1)/2。堆排序分两步走第一步把整个数组建成大顶堆保证堆顶元素是最大值第二步把堆顶元素和数组末尾交换交换后堆的长度减一再对新的堆顶做“下沉调整”。// 下沉调整把以root为根的子树调整为大顶堆 void heapify(int arr[], int n, int root) { int largest root; int left 2 * root 1; int right 2 * root 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! root) { int tmp arr[root]; arr[root] arr[largest]; arr[largest] tmp; 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--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } }初学堆排序最常见的疑问是“为什么要从n/2-1开始建堆”。因为最后一个非叶子节点的下标就是n/2-1它的子树至少有两个节点需要调整而下标更大的都是叶子节点单节点天然满足堆的性质不需要调整。从右到左、从下到上把所有非叶子节点调整一遍数组就变成了大顶堆。堆排序的优点很硬原地排序、空间复杂度O(1)、最坏情况也是O(n log n)不存在快排那种退化风险。缺点是常数系数大实际运行通常比快排和归并慢并且它是不稳定排序交换堆顶和末尾元素时会打乱相等元素的相对顺序。面试里还经常把堆排序当作“快速求前K个最大/最小元素”的敲门砖。因为建堆是O(n)之后每次取堆顶并调整是O(log n)取K个元素的整体复杂度是O(n K log n)远好于先全排序再取前K个。4. 非比较排序的课代表计数排序及其适用范围4.1 计数排序的核心逻辑所谓“排序”其实是“统计”讨论计数排序前先明确它的使用前提数据必须是非负整数或者能映射成非负整数并且数据范围k不能太大否则空间开销会爆炸。它不走“比较元素大小”的路线而是利用数组下标天然有序这个特性直接把元素值当作下标来统计频次。我第一次学计数排序的时候最大的震撼是它只有三步统计每个值出现几次把频次转成“每个值最终应该占据的位置”前缀和从原数组末尾开始遍历按前缀和把每个元素放到结果数组的正确位置并减一。第三步为什么要从末尾开始因为要保证稳定性——相等元素的后一个会先被放入结果数组的靠后位置再处理前一个时前缀和已经减一正好落到靠前的位置。void countingSort(int arr[], int n) { if (n 1) { return; } // 先找到最大值假设所有元素非负 int maxVal arr[0]; for (int i 1; i n; i) { if (arr[i] maxVal) { maxVal arr[i]; } } int countSize maxVal 1; int *count (int *)calloc(countSize, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); // 第一步统计频次 for (int i 0; i n; i) { count[arr[i]]; } // 第二步前缀和count[i]表示值i的元素总数 for (int i 1; i countSize; i) { count[i] count[i - 1]; } // 第三步从后往前放置保证稳定性 for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } // 拷回原数组 for (int i 0; i n; i) { arr[i] output[i]; } free(count); free(output); }时间复杂度是O(n k)当k和n同数量级时近似O(n)这是比较类排序做不到的。但它的代价也明显需要额外的O(k)计数数组和O(n)结果数组。如果最大值是1000000而实际只有10个数那计数排序就非常不划算因为光初始化计数数组就要遍历100万个位置。这种场景应该用其他排序。4.2 计数排序、基数排序和桶排序的关联市面上“8种排序算法”的说法里第八种有时候是基数排序有时候是桶排序我习惯先把计数排序讲清楚因为它刚好是后面两者的基石。基数排序把数据按“位”拆开先按个位排再按十位排需要保证每一趟里都用稳定排序。这里重点不是排序本身而是“必须稳定”这一约束——上一趟处理过的顺序在下一趟不能被打乱。每一位内部用计数排序稳定处理最合适。桶排序把数据均匀分到几个桶里每个桶内部再用其他排序算法最后按桶顺序合并。它适合数据分布比较均匀的场景比如浮点数在[0,1)区间均匀分布。这三兄弟通常出现在面试加分项或考研选择判断题里不需要把代码写得滚瓜烂熟但一定要能说清楚“非比较排序为什么能突破O(n log n)的下界”以及“它为什么有严格的使用条件”。突破下界靠的是用空间换时间使用条件苛刻则是它无法全面替代比较类排序的根本原因。4.3 计数排序的边界与陷阱计数排序的使用有几个容易被忽略的边界负数怎么办元素值不能直接做下标解决办法是所有值统一减去最小值minVal把值域平移成[0, maxVal - minVal]最后输出时再加回minVal。这部分代码很简单但考卷上不说明的话很多人会在这一步翻车。稳定性验证。我用下方案例验证过输入[2a, 1, 2b]计数数组先统计随后从后往前放置。原数组最后一个2b先被放入结果末尾然后1放入中间最后2a放入开头。这样2a仍然排在2b前面做到了稳定。很多资料上只写“计数排序是稳定的”并没有解释为什么必须从后往前放这个细节值得你动手推演一遍。内存分配。计数排序的时间虽然快空间却是O(n k)在嵌入式或内存受限的环境里可能直接把程序干崩。代码里务必记得释放动态分配的数组否则就算排序没问题LeetCode的C语言提交也会判你Memory Leak。5. 实战选型真实场景里到底该用哪个排序5.1 不同数据特性下的算法推荐速查学了8种算法之后最大的痛苦往往不是“学不会”而是“不知道该用哪个”。我在做实际项目时总结过一套快速选型的判断流程分享出来供参考数据特征推荐算法理由数据量很小几十个以内插入排序实现简单常数系数极低无需额外空间数据基本有序逆序对很少插入排序最好情况O(n)比快排的递归开销小数据量大且完全随机快速排序平均性能最优统计算法中的标杆数据量大但要求稳定归并排序O(n log n)与稳定性兼得可牺牲O(n)空间数据量大但内存紧张堆排序原地排序最坏也是O(n log n)数据范围很小如0~100成绩计数排序线性时间秒杀一切比较类算法需要排序链表归并排序不需要随机访问链表归并是最自然的方案数据库/外部文件排序归并排序多路归并内存装不下全部数据只能分段内存排序后归并一眼就能看出快排和堆排是面试的重点插入和归并是工程的重点。即便你在业务里直接调用Arrays.sort()或qsort底层源码涉及到的优化思想也无非是前面说的这些小规模用插入排序兜底、快排partition遇到恶劣数据切换堆排序、归并把额外空间控制在O(n)以内。5.2 面试中的排序算法考察套路面试官问排序的时候通常不会直接让你机械地写某个排序而是喜欢换着花样考。我整理了几个高频套路“说说快排的优化方案”。参考答案要覆盖三数取中、随机选pivot、小区间改插入排序、递归改迭代防栈溢出。只说一个“随机选基准”就有单薄最好把三数取中和插入排序收尾也带上。“归并排序的空间复杂度是多少能不能原地归并”。原地归并理论上可行但常数极大实际工程基本不这么干所以不要为了炫技硬上老老实实回答“经典实现是O(n)原地版本会牺牲性能”反而稳妥。“求数组第K大的元素”。可以用快排的partition思想平均O(n)也可以用大小为K的小顶堆O(n log K)。这两种解法对应着两种排序思想都是考点。“为什么稳定排序在某些场景下不可或缺”。经典案例是多关键字排序先按姓名排序再按成绩排序如果第二次使用的是不稳定排序之前姓名的顺序就全乱了。5.3 从实现细节反推算法稳定性还有一个边界情况值得单独拎出来同样是插入排序如果你在实现时把while (j 0 arr[j] key)写成了arr[j] key那么相等元素也会往前走稳定性就被暗中破坏了。反之变只是影响了相等元素的处理方式不会让别的指标变差。这个细节可以在写代码时自测用一个含有重复元素的数组给每个元素加上位置标签排序完后检查相同值的标签顺序是否保持原序就能验证算法是否稳定。自测这招比你背“哪些算法稳定”靠谱得多尤其到了研究生复试或大厂二面考官会让你现场写一个验证稳定性的测试用例。6. 常见问题与排错经验从实战中踩过的坑6.1 快速排序的退化问题从O(n log n)变成O(n²)快排退化是面试中最常被拎出来说的话题我当年亲身吃过一次亏。那次是给一个已经升序排列的数组做排序我用了Lomuto划分并直接取最后一个元素当基准结果递归深度直接变成n不仅慢到卡顿还差点把栈顶爆掉。排查思路很简单对有序或近乎有序的输入检查自己选基准的代码是不是固定取了arr[high]。如果是立刻把基准选择改成“三数取中”下标low、mid、high对应值的中位数与最后一个元素交换其余逻辑不变。三数取中能把最坏情况的概率降到极低。如果还想更稳可以直接用rand()随机选一个下标作为基准代价是多了个随机数函数调用。6.2 归并排序的merge边界一不留神就数组越界归并排序的坑几乎都集中在merge函数的下标上。最常见的两个错误一是mid的计算写成(left right) / 2当left和right都很大时可能整数溢出应该写成left (right - left) / 2二是在合并后的拷贝循环里写了for (int p 0; p right; p)把临时数组的起点忘了加left。调试时有个土办法在merge函数开头打印left、mid、right若出现left大于mid、或mid大于right的情况说明递归边界传参有误。这种问题别看代码短定位起来能把人磨到怀疑人生所以最好把merge和mergeSort的参数统一成“左闭右闭区间”全代码里只用这一种区间风格不要混着用。6.3 堆排序的递归栈与建堆起点堆排序里最容易写崩的是heapify的递归调用忘了加“子树大小不能超过当前堆大小”的判断。我见过太多人把第二个参数直接写成数组总长度n导致在进行到堆长减小时交换回来的元素又被错误地调回了堆顶。这段代码在LeetCode上跑测试时建议单独写一个判断函数排序结束后用for (int i 1; i n; i)校验arr[i-1] arr[i]。如果发现末尾的元素顺序不对优先排查heapify的n有没有跟着缩小。6.4 稳定性陷阱选择了稳定排序却写出了不稳定代码这个话题比较有意思。类如“快速排序不稳定”“堆排序不稳定”这类结论大家都能背但如果是稳定排序比如插入排序或归并排序很多人会觉得“既然是稳定排序代码怎么写都稳”于是写出我刚才提过的版本破坏了稳定性。排查技巧给数组元素加上id字段作为第二关键字排序完后检查重复值对应的id数组是否保持升序。这一步能自动检测你的实现是否真正稳定建议每个排序都跑一遍既加深理解也能发现很多你看不到的隐性bug。我通常在本地写一个小测试函数一次性输入8组含相同值的数据分别验证稳定性效果很好。6.5 计数排序的k值过大导致内存崩溃遇到过大k值导致内存崩溃是计数排序最实际的坑。我在真实项目里过滤了一批HTTP状态码数据状态码的取值虽然只有几十种但用户自定义的时间戳却达到了亿级。如果按偏移量直接开数组内存直接爆炸。这里的经验是适当压缩值域后再用计数排序。处理办法是先把数据做一次映射把稀疏的大整数映射成连续稠密的小整数然后排序最后再映射回去。值域确实大到无法压缩时果断放弃计数排序改用基数排序它会大大缓解空间压力。7. 写在最后按自己的思路把8种算法串成一条线梳理完这8种排序算法后再回头看开头的表格你会发现自己已经不再需要死记那些复杂度数字了。冒泡和选择为什么是O(n²)归并和快排为什么是O(n log n)计数排序为什么是O(n k)每一列背后都有了一套解释体系这才是我写这篇文章最想让你拿走的东西。我个人在实际操作中体会最深的一条经验是永远不要单独记一个算法而是把它放进和其他算法的对比里记。快排和归并都是分治区别在于分的过程做多少事归并的划分是O(1)级别的“切一刀”排序动作全在合并快排则相反划分时做了大量交换合并时几乎无事可做。希尔排序是插入排序的“大步走版本”堆排序其实是选择排序的“高级版本”只是不用每次线性扫描找最大元素而是用堆这个结构把查找最大值的代价从O(n)降到了O(log n)。想通了这几组对比你的知识结构就不再是一个一个孤立的代码片段而是一张张彼此关联的图。最后送你一个学习建议看完这篇别急着写下一个算法先手写一份包含重复元素的白板测试数据把冒泡、插入、归并、计数这四个稳定排序的稳定情况验一遍再把快排、堆排的不稳定情况找出来。这个动手过程比任何资料都能帮你把“稳定性”这三个字刻进脑子里。数据结构这门课没有太多捷径硬啃加动手验证才是唯一的捷径。