数据结构复习（第八章）：排序

排序从局部有序到整体有序的一整套方法理解这一章讨论的是排序。表面上看排序似乎只是把一组记录按关键字从小到大或从大到小重新排好但真正学到后面会发现排序远不只是“调整顺序”这么简单。它实际上是在研究为了让数据变得有序我们能怎样利用已有结构、怎样减少比较与移动、怎样在时间、空间和稳定性之间做取舍。这一章通常会先讲排序的基本概念说明内排序、外排序、稳定性、时间复杂度等评价维度再进入插入排序、交换排序、选择排序、归并排序、基数排序等几大类经典方法最后结合性能分析比较不同排序算法各自适合什么场景。真正理解之后你会发现这一章并不是一串孤立算法而是一条很清晰的思路演化链从最朴素的局部调整开始逐步发展到更高效的分治、堆结构和非比较排序方法。一、排序的本质让记录之间的次序满足目标关系所谓排序就是把一组记录按照关键字递增或递减重新排列使它们满足给定的有序关系。若把关键字看作比较依据那么排序算法本质上就在做两件事一是比较哪些元素先后应当调整二是通过移动或交换把这些元素放到更合适的位置。这一定义看起来很直接但里面有两个特别重要的点。第一排序的对象不一定只是数字也可以是任意带关键字的记录。第二排序关注的不只是“结果有序”还包括“排序过程付出了多大代价”。也就是说排序问题从来不是只问“能不能排好”而是要问“排得快不快、稳不稳、占不占空间”。也正因为如此教材在一开始就会强调几个评价标准时间复杂度、空间复杂度、稳定性以及内排序和外排序的区别。后面所有具体算法其实都可以回到这几个维度来理解和比较。二、内排序与外排序区别在于数据能不能一次装进内存排序方法首先会区分为内排序和外排序。内排序指的是待排序记录可以全部放入内存中完成排序外排序则用于数据规模很大、无法一次全部放入内存需要借助外存分批处理。这一章的大部分内容都属于内排序。因为教材重点是在有限内存环境下研究各种经典算法的思想与性能。像插入排序、冒泡排序、快速排序、堆排序、归并排序、基数排序等通常都被归入内排序的讨论范围。理解这个区分很重要因为它提醒我们排序算法并不是脱离硬件环境抽象存在的。数据规模和存储环境不同会直接影响排序策略。也正因为如此后面讲到归并排序和 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)。第三要区分是否需要额外空间。归并排序和基数排序通常需要较多辅助空间而堆排序的辅助空间通常较少。第四要区分“利用已有序性”的能力。直接插入排序和冒泡排序在序列接近有序时往往表现较好而快速排序、堆排序这类方法对初始有序程度并没有那么强的正向利用。这些比较题看起来零散其实都在围绕一个共同问题每种算法为了换取某种优势付出了什么代价。结语这一章表面上讲的是“如何把一组数据排好”实际上讲的是算法设计中非常核心的一件事面对同一个目标可以采用完全不同的组织与推进方式。有的算法依赖局部插入有的依赖交换划分有的依赖树形结构有的依赖合并过程还有的干脆绕开比较直接利用关键字内部信息。真正把这一章学懂之后收获不会只是会写几种排序代码而是会逐渐形成一种更高层次的判断力当一个问题需要整理全局顺序时究竟该通过局部调整、分治拆分、结构辅助还是直接映射来解决。到这一步排序就不再只是数据结构课程中的一章内容而会变成理解算法思想差异的一扇非常重要的窗口。重点问题