排序：从局部有序到整体有序的一整套方法理解
这一章讨论的是排序。表面上看，排序似乎只是把一组记录按关键字从小到大或从大到小重新排好，但真正学到后面会发现，排序远不只是“调整顺序”这么简单。它实际上是在研究：为了让数据变得有序，我们能怎样利用已有结构、怎样减少比较与移动、怎样在时间、空间和稳定性之间做取舍。
这一章通常会先讲排序的基本概念，说明内排序、外排序、稳定性、时间复杂度等评价维度；再进入插入排序、交换排序、选择排序、归并排序、基数排序等几大类经典方法；最后结合性能分析，比较不同排序算法各自适合什么场景。真正理解之后，你会发现这一章并不是一串孤立算法，而是一条很清晰的思路演化链：从最朴素的局部调整开始，逐步发展到更高效的分治、堆结构和非比较排序方法。
一、排序的本质：让记录之间的次序满足目标关系
所谓排序，就是把一组记录按照关键字递增或递减重新排列，使它们满足给定的有序关系。若把关键字看作比较依据，那么排序算法本质上就在做两件事：一是比较哪些元素先后应当调整，二是通过移动或交换把这些元素放到更合适的位置。
这一定义看起来很直接，但里面有两个特别重要的点。第一，排序的对象不一定只是数字，也可以是任意带关键字的记录。第二，排序关注的不只是“结果有序”，还包括“排序过程付出了多大代价”。也就是说，排序问题从来不是只问“能不能排好”，而是要问“排得快不快、稳不稳、占不占空间”。
也正因为如此，教材在一开始就会强调几个评价标准：时间复杂度、空间复杂度、稳定性，以及内排序和外排序的区别。后面所有具体算法，其实都可以回到这几个维度来理解和比较。
二、内排序与外排序，区别在于数据能不能一次装进内存
排序方法首先会区分为内排序和外排序。内排序指的是待排序记录可以全部放入内存中完成排序；外排序则用于数据规模很大、无法一次全部放入内存，需要借助外存分批处理。
这一章的大部分内容都属于内排序。因为教材重点是在有限内存环境下研究各种经典算法的思想与性能。像插入排序、冒泡排序、快速排序、堆排序、归并排序、基数排序等，通常都被归入内排序的讨论范围。
理解这个区分很重要，因为它提醒我们：排序算法并不是脱离硬件环境抽象存在的。数据规模和存储环境不同，会直接影响排序策略。也正因为如此，后面讲到归并排序和 B 树之类内容时，会越来越明显地看到“算法设计总是和存储条件绑定”的思想。
三、稳定性不是附属概念，而是排序的重要性质
稳定性是排序章节中非常核心却也非常容易被忽视的概念。若待排序序列中存在多个关键字相等的记录，排序后这些记录的相对次序保持不变，则称该排序算法是稳定的；否则称为不稳定排序。
这个概念之所以重要，是因为很多实际记录并不只有一个字段。比如先按成绩排序，再按学号排序，或者先按部门排序，再按入职时间排序，这时前一次排序形成的相对顺序是否会被打乱，就会直接影响最终结果。稳定排序能够在“关键字相等”的情况下保留原有顺序，因此特别适合多关键字排序场景。
后面学每一种算法时，不要只盯着快不快，还要顺手问自己一句：它稳定吗。你会发现，这个问题往往和算法内部到底是“交换”为主、“插入”为主，还是“合并”为主密切相关。
四、插入排序：把无序部分的元素逐步插入到已有序序列中
插入排序的基本思想非常自然。可以把待排序序列看成前面一段已经有序、后面一段尚未处理。每次从无序部分取出一个元素，把它插入到前面那个已经有序的子序列中的合适位置。经过不断重复，已排序区间逐渐扩大，最终整个序列有序。
直接插入排序是这一类中最基本的方法。它的过程很像打扑克牌时整理手牌：新拿到一张牌，就把它插入到当前已经排好顺序的位置中。若原序列本身已经接近有序，那么每次插入时移动距离很短，因此效率会比较好；但若原序列完全无序甚至逆序，则为了给新元素腾位置，可能要移动很多记录，因此最坏时间复杂度是 O(n²)。
直接插入排序的一个很重要特点是稳定。因为它在插入时通常只会把比待插入元素大的记录向后移动，而不会跨过相等关键字记录的原有顺序。也正因为如此，它在数据量不大、原序列基本有序的场景下，往往是一种简单而实用的选择。
五、折半插入排序：优化的是查找位置，不是移动代价
直接插入排序中，一个显著开销来自“找到插入位置”这一过程。为了减少比较次数，可以在已经有序的部分中使用折半查找来定位插入位置，这就形成了折半插入排序。
它相对于直接插入排序的改进，在于比较次数减少了。因为有序区中插入位置可以通过二分定位，所以查找插入点的成本从线性级降低到了对数级。但要注意，它并没有减少元素移动次数。因为一旦插入位置确定，后面比它大的元素仍然要整体后移，才能空出位置。
因此，折半插入排序虽然在比较次数上优于直接插入排序，但整体时间复杂度在数量级上通常仍然是 O(n²)。这部分内容特别适合理解一个常见现象：算法优化不一定总能改变大 O 数量级，有时只是优化了某个局部代价，但若主导成本没变，整体数量级也就不会变。
六、希尔排序：通过缩小增量，让远距离逆序先被消化
希尔排序可以看作对插入排序的一次重要改进。它的核心思想是：直接插入排序之所以在逆序严重时效率不高，是因为元素每次只能一点点往前挪。那能不能先让相距较远的元素提前比较和调整，把“大逆序”先消化掉，再在最后做一次细致整理？
于是希尔排序引入了“增量”概念。先按某个较大的步长把序列划分成若干子序列，对每个子序列分别做插入排序；然后逐步缩小增量，继续对子序列做插入排序；最后当增量缩小到 1 时，再做一次普通插入排序。因为前面几轮已经让序列整体上变得更接近有序，所以最后这次插入排序会高效得多。
希尔排序的关键在于增量序列的选择，不同增量方案会影响最终性能。它通常是不稳定排序，因为跨步长分组时，相同关键字记录的原始相对位置可能被打乱。就整体思想而言，它最大的价值在于展示了一种很重要的改进路线：先做粗调整，再做细调整，让局部有序逐步向整体有序过渡。
七、交换排序：通过逆序元素交换逐步逼近有序
交换排序的基本思想，是通过比较两个记录的关键字，若它们顺序不符合要求，就交换它们的位置。看起来很朴素，但其中又可以分为代表性很强的两种方法：冒泡排序和快速排序。
1. 冒泡排序：让较大元素逐趟“浮”到后面
冒泡排序是最直观的交换排序。它从序列的一端开始，依次比较相邻元素，若前者大于后者就交换。经过一趟扫描后，最大元素会逐步“冒”到序列末尾；再对前面剩余部分重复同样操作，第二大元素又会被放到倒数第二个位置，以此类推。
它的过程很容易理解，也便于实现，而且是稳定排序，因为交换通常只发生在严格逆序的相邻元素之间，相等关键字不会跨越彼此。但它的效率并不高。平均和最坏时间复杂度通常都是 O(n²)，因此在大规模数据上并不实用。
不过冒泡排序并不是毫无价值。它最适合帮助理解“逆序对减少”和“局部交换推动整体有序”的过程。教材中常会提到，若某一趟扫描没有发生交换，就说明序列已经有序，可以提前结束。这体现了冒泡排序对“几乎有序”数据的某种自适应性。
2. 快速排序：通过划分把问题分治下去
快速排序是交换排序中真正高效的方法之一，也是整章最重要的算法之一。它的核心思想不是简单反复交换，而是先选取一个枢轴元素，把序列划分成两部分：一部分都比枢轴小，另一部分都比枢轴大。这样，枢轴就被放到了最终应该在的位置上。随后再对左右两部分递归地进行同样处理，直到整个序列有序。
快速排序真正强大的地方，在于它利用一次划分就把问题拆成了两个相互独立的子问题。这种“分而治之”的思想和前面的顺序调整完全不同。若每次划分都比较均匀，那么递归深度大约是 O(log n)，每一层又大约处理 O(n) 个元素，因此平均时间复杂度可达到 O(n log n)。
但快速排序也有弱点。若每次选到的枢轴都非常糟糕，比如原序列本身接近有序、而枢轴总是取到最左或最右元素，那么划分会极不均匀，递归会退化，最坏时间复杂度可达到 O(n²)。此外，快速排序通常是不稳定的，因为划分过程中可能会发生跨区域交换。
快速排序之所以经典，不只是因为它快，更因为它第一次把排序问题非常完整地展现为一个分治模型。后面很多高级算法思路，其实都能和这种“先划分，再递归处理”的思想对应起来。
八、选择排序：每一趟确定一个最终位置
选择排序的基本思想是：每一趟在未排序区中选出最小或最大的元素，把它放到当前应该放置的位置上。经过第一趟后，最小元素就在第一个位置；第二趟后，次小元素在第二个位置；如此反复，最终整个序列有序。
简单选择排序的一个特点是交换次数少。因为每一趟通常只在最后进行一次交换，所以总交换次数大约是 O(n)。但它的比较次数并不低。为了找出当前最小元素，每一趟都要扫描剩余未排序部分，因此总体时间复杂度仍然通常是 O(n²)。
简单选择排序通常是不稳定的。因为当某个后出现的较小元素与前面元素交换时，相同关键字记录的相对次序可能会被改变。它的价值更多体现在思路上：和插入排序每次处理一个元素不同，选择排序每次确定一个最终位置。也就是说，它优化的是“目标位置逐步落实”的过程，而不是通过局部有序不断扩张。
九、堆排序：借助完全二叉树结构高效选择最大或最小元素
堆排序是在选择排序思想上的一次结构性升级。简单选择排序虽然也是每次选出当前最大或最小元素，但为此通常要线性扫描整个未排序区。那能不能让“选最大值”这件事变得更快？于是就引入了堆这种结构。
堆本质上是一种完全二叉树，满足堆序性质。大根堆要求每个结点都不小于其孩子结点，因此根结点一定是当前序列中的最大值；小根堆则相反。这样一来，每次只要把根取出来放到序列末尾，再对剩余部分重新调整成堆，就能继续得到下一个最大值。
堆排序通常分两步：先把原序列建成堆，再反复执行“取堆顶 + 重新调整堆”。由于建堆和每次下滤调整都可以较高效地完成，所以堆排序的时间复杂度通常为 O(n log n)，且最坏情况下也能保持这一数量级。这一点是它相对快速排序的一大优势。
不过堆排序通常是不稳定的，因为调整堆时会发生跨层交换，相等关键字的原始相对次序难以保持。它最值得理解的地方在于：它把“每次找最大值”的问题，借助完全二叉树结构优化成了对数级调整。这是数据结构为算法服务的一个非常典型例子。
十、归并排序：先排好局部，再把局部有序合并成整体有序
归并排序是分治思想在排序中的另一种代表。它的核心思路是：若一个大序列不好直接排，可以先把它拆成两个较小子序列，分别排好序，再把两个有序子序列合并成一个更大的有序序列。如此递归下去，直到子序列长度为 1，再从底向上不断合并，最终完成排序。
归并排序最关键的操作是“归并”。若两个子序列本身已经有序，那么只要设置两个指针，反复比较当前较小元素，把更小者依次放入辅助空间，就能在线性时间内完成合并。也就是说，归并排序真正依赖的不是神奇交换，而是“两个有序序列能够高效融合”这一性质。
归并排序的时间复杂度通常稳定在 O(n log n)，而且无论最好、平均还是最坏情况都较稳定。它还是稳定排序，因为合并时相等关键字记录可以按原有先后顺序依次取出。
它的主要代价在于需要额外辅助空间，尤其在数组实现中通常需要 O(n) 级别的额外空间。即便如此，归并排序依然非常重要，因为它把“有序块不断合成更大有序块”的思想表现得极其清楚，也为后面的外排序打下了基础。
十一、基数排序：跳出比较框架，按位或按关键字分配收集
前面讲过的大多数排序方法，本质上都属于比较排序，也就是说，它们通过关键字之间的大于、小于关系来决定顺序。而基数排序则走了一条不同的路：不直接比较关键字大小，而是按关键字的某一位或某一部分进行分配和收集。
以多关键字或多位数排序为例，可以从最低位到最高位依次进行稳定分配。每一趟按当前位的取值把元素分到若干桶中，再按桶的顺序收集回来。由于每一趟都保持稳定，低位上已经形成的相对顺序不会被高位操作破坏。经过若干趟之后，整个序列就有序了。
基数排序的一个突出特点是，它不依赖关键字之间的直接比较，因此不受比较排序下界 O(n log n) 的限制。在适当条件下，它的效率可以非常高。但它也不是万能的。它通常要求关键字结构适合拆分，比如整数位数、字符串字符位、多关键字字段等；同时还需要额外桶空间，因此适用场景有一定限制。
这一方法特别值得单独拎出来理解，因为它让人看到：排序并不只有“比较后交换”这一条路。只要能利用关键字的内部结构，也可以设计出完全不同风格的排序算法。
十二、各种排序算法的比较，真正要看的是“场景适配”
学完这么多算法后，最容易出现的问题，就是把它们看成一堆并列的模板。其实排序章节最重要的能力，不是会背代码，而是知道什么场景下谁更合适。
如果数据量小、而且原序列基本有序，直接插入排序往往表现不错，因为实现简单且移动代价不大。若希望利用“远距离调整”改进插入过程，可以考虑希尔排序。若只是想理解最基础的交换和选择思想，冒泡排序和简单选择排序最合适，但它们在大规模数据上通常不是首选。
若希望平均性能优秀，快速排序往往是非常经典的选择；若要求最坏情况下也保持 O(n log n)，堆排序和归并排序更稳妥。若还要求稳定性，归并排序通常比堆排序和快速排序更有优势。若关键字适合按位处理，且不想受比较排序下界限制，则基数排序可能特别有效。
也就是说，排序算法并没有绝对的“最好”，只有针对不同需求的“更适合”。而教材在整章中不断比较时间复杂度、空间复杂度和稳定性，真正目的就是培养这种选择意识。
十三、比较排序与非比较排序，体现了两类不同思维
如果从更高一层看，这一章实际上展示了两种非常不同的排序思路。
一类是比较排序。像插入排序、冒泡排序、快速排序、选择排序、堆排序、归并排序，都建立在关键字比较基础上。它们通过比较决定元素相对位置，再借助插入、交换、选择、合并等方式逐步形成有序序列。
另一类是非比较排序。基数排序是其中最典型的例子。它不关心“a 是否大于 b”，而是关心“当前位是多少”“应该进哪个桶”。这种方法利用的是关键字内部结构，而不是关键字之间的大小关系。
这一对比很重要，因为它会帮助你真正理解排序算法的边界在哪里。不是所有排序都受同一复杂度规律限制，也不是所有排序都只能靠比较驱动。算法的多样性，恰恰来自于它们抓住的信息不同。
十四、这一章最容易混淆的地方，常常都和“性质判断”有关
排序章节最容易出错的，不是代码背错，而是性质分不清。
第一，要区分稳定与不稳定。插入排序、冒泡排序、归并排序、基数排序通常是稳定的；快速排序、简单选择排序、堆排序、希尔排序通常是不稳定的。真正判断时，不要靠死背，而要想一想过程中会不会让相等关键字记录跨越彼此。
第二，要区分平均复杂度和最坏复杂度。快速排序平均很优，但最坏可能退化；堆排序和归并排序在最坏情况下也能维持 O(n log n)。
第三，要区分是否需要额外空间。归并排序和基数排序通常需要较多辅助空间，而堆排序的辅助空间通常较少。
第四，要区分“利用已有序性”的能力。直接插入排序和冒泡排序在序列接近有序时往往表现较好，而快速排序、堆排序这类方法对初始有序程度并没有那么强的正向利用。
这些比较题看起来零散，其实都在围绕一个共同问题：每种算法为了换取某种优势，付出了什么代价。
结语
这一章表面上讲的是“如何把一组数据排好”，实际上讲的是算法设计中非常核心的一件事：面对同一个目标，可以采用完全不同的组织与推进方式。有的算法依赖局部插入，有的依赖交换划分，有的依赖树形结构，有的依赖合并过程，还有的干脆绕开比较，直接利用关键字内部信息。
真正把这一章学懂之后，收获不会只是会写几种排序代码，而是会逐渐形成一种更高层次的判断力：当一个问题需要整理全局顺序时，究竟该通过局部调整、分治拆分、结构辅助，还是直接映射来解决。到这一步，排序就不再只是数据结构课程中的一章内容，而会变成理解算法思想差异的一扇非常重要的窗口。
