动机
排序算法可利用不同信息。插入排序受益于近乎有序的输入;随机化快速排序避免固定输入排列决定表现,但仍可能执行缓慢。计数与基数排序利用整数键结构,而非仅通过比较获取次序。分析须说明利用的优势及其成本。
上一章已证明归并排序及比较下界。本章分析逆序对造成的移动成本、随机性改变的复杂度陈述,以及按位排序为何需要稳定性。
定义
定义 8.1.1
(记录、稳定性与逆序对)
输入是记录序列 ,其键取自全序集。正确的排序算法按键的非降序返回同样的这些记录。若键相等的记录保持其原有的相对顺序,则称该排序是稳定的。逆序对是满足 且 的一对位置。设 为此类位置对的个数;键相等的记录对不构成逆序对。
最坏情况界适用于每一个允许的输入和每一种随机结果。随机化算法的期望界是对固定输入在其内部随机选择上取平均;它并不假设输入本身是随机抽取的。比较次数指键的比较次数。在下面使用的运算模型中,数组访问、下标运算以及移动一个固定大小的记录都视为常数代价的操作。
对于计数排序,键是 中的整数,其中 。对于基数排序,键有 个 进制数位,其中 ,必要时以前导零补齐。在此模型中,访问数位被假定为常数代价。这些假设是额外的信息,并不是全序本身的推论。
定理/命题
定理 8.1.2
(插入排序对逆序对具有适应性)
仅当较前记录的键严格大于被插入的键时才将其右移的插入排序是稳定且正确的。在数组实现中,对 ,它恰好进行 次记录移动,运行 次操作。其最坏情况代价为 ,而已经有序的输入仅需 。
定理 8.1.3
(随机化快速排序的期望比较次数)
假设 个键互不相同。每个递归子问题从其自身的记录中均匀随机地选取枢轴,划分时将该枢轴与子问题中其余每个记录各比较一次。设 。对 ,键比较的期望次数为
因此,对 ,期望操作次数为 ,其中划分工作量为线性。最坏情况仍为 。
定理 8.1.4
(稳定计数排序与最低位优先基数排序)
采用累计端点计数并从右向左扫描放置的计数排序是稳定且正确的,时间为 ,辅助空间为 。从最低位到最高位依次施行稳定的数位排序,可对定宽键排序。每个数位都使用计数排序时,时间为 ,辅助空间为 。
证明思路或证明
证明
(插入排序的正确性、稳定性与移动次数)
插入排序从左到右处理各位置。在插入下一个记录之前,较前的前缀是原前缀的一个有序排列。将其中较大的键右移,直到被插入的键可以放在所有不超过它的键之后。此时前缀再次有序,且包含相同的记录。归纳法证明其正确性。相等的键从不被移到彼此之后,这就证明了稳定性。
关于移动次数,可以把每次移动想象成被插入记录与紧邻其前且更大的记录交换。对一个逆序的相邻记录对做相邻交换,恰好消除一个逆序对。由于被交换的两个记录相邻,它们与任何第三个记录的关系都不会改变逆序对的总数。算法结束时没有逆序对,所以移动的总次数恰好等于原来的逆序对个数。每一次成功的内层比较都导致一次移动;每次插入至多多出一次失败的键比较。外层迭代与放置只增加线性的工作量,从而得到 的上下两个界。
证明
(按名次对计算期望比较次数)
对于快速排序,用最终名次 标记这些互不相同的键。名次为 的两个键被比较,当且仅当从名次 中最先被选为枢轴的是这两个端点之一。该区间之外的枢轴无法将两个端点分开。区间内部的枢轴会将它们永久分开;端点枢轴则直接比较它们。区间内每个键成为其首个枢轴的可能性相同,所以比较概率为 。
令指示变量在该对被比较时取一,否则取零。一对键至多被比较一次,因为比较之后其中一个记录已作为枢轴被移出。期望的线性性(不要求各指示变量相互独立)给出
积分界 说明了所述的渐近增长。反之,若每次都选取极端枢轴,则共有 次比较,所以二次的执行仍然可能出现。
证明透视
对哪一种随机性取平均?
关键一步是按名次对计数,而不是跟着递归走:名次 的两个键是否被比较,只取决于名次 之中哪一个最先被选为枢轴,因为区间之外的枢轴会把两个键送到同一侧。枢轴均匀选取,使这 个键各有相同的机会最先被选中;键互不相同,使名次有定义,且每个枢轴都做严格划分。然后由期望的线性性完成论证,并不需要各个键对事件之间相互独立。
固定完整的输入顺序,只对枢轴的选择取平均。键互不相同与枢轴均匀这两个假设,保证了端点概率 ;它们不是计算中可有可无的细节。
证明
(计数排序与基数排序的正确性)
对于计数排序,首先统计每个键的频数,并构造累计端点 ,即键不超过 的记录个数。键 属于分配给它的连续区块。从右向左扫描输入;将键为 的记录放在输出位置 ,然后将 减一。每次放置都使用该键区块中最右边仍为空的位置。所有记录都被放入有序的区块。在键相等的记录中,原来最靠右的记录被放在最右边,因此保持了它们的顺序。
对于基数排序,经过 趟稳定排序后,记录已按其最低 位数位有序。下一趟对新的数位排序。在新数位相同的各组内,稳定性保持了先前低位的顺序,于是记录按最低 位数位有序。零趟时的断言是空洞成立的;对所有数位进行归纳即证明正确性。时间与空间的界由各趟计数排序的代价相加并重复使用存储空间得到。
例题详解
例题 8.1.5
(四个逆序对,四次插入移动)
取键 ,下标用于区分键相等的记录。第一个键大于其后三个键,给出三个逆序对;键二大于其后的 ,再给出一个。插入 时将三右移一次;插入二时将三右移一次;插入 时将三与二右移。四次移动得到 。严格比较使 仍在 之前,这除了说明有序之外,还展示了稳定性。
例题 8.1.6
(期望代价并非每次运行都能达到的代价)
对于三个互不相同的键,选到中间名次作枢轴的概率为 ,用两次比较。选到极端名次的概率为 ,总共需要三次比较。因此期望为 ,与 相符。单次运行使用两次或三次比较,绝不会恰为 次。这个非整数的期望描述的是对各次执行的平均,而不是一次执行中的分数工作量。
例题 8.1.7
(端点计数与反向放置)
对于键 ,键的全集为 ,频数为 ,累计端点为 。反向扫描时,键一放在位置一, 放在位置三,零放在位置零, 放在位置二。输出为 。若用同样递减的端点做正向扫描,则会使键二的两个记录颠倒顺序,所以扫描方向是稳定性证明的一部分。
稳定性是记录的可观察性质
仅显示相等数值会掩盖不稳定性,因为交换它们不改变显示的数值序列。按原始位置区分记录便可观察稳定性。正确排序要求键有序,稳定性还要求记录间的原有次序;前者不能推出后者。
稳定排序能保留次要键次序:若已按次要键排序,再按主键稳定排序,则每个主键组内的次序不变。最低位优先基数排序正是使用这一机制;只保证每趟数位有序还不足以证明算法正确。
计数排序还须统一下标。累计端点记录个数,减一才得到从零开始的放置位置;递减后表示该块剩余的可用位置。若从一开始编号,表达式不同而区块不变量相同。混用约定会造成差一错误,这与频数计数本身无关。
适应性、期望与最坏情况回答的是不同的问题
插入排序的逆序对界确定性地适用于实际输入。若逆序对很少,那么这一次具体的运行就很快。随机化快速排序的期望界适用于每一个键互不相同的固定输入,但它是对内部选择取平均。罕见的糟糕枢轴序列仍可能很慢。两个陈述互不蕴含,也都不改变最坏情况量词的含义。
为了说明对枢轴规则的依赖,考虑有序输入、总是选择第一个记录的规则,并要求划分保持各递归部分内部的相对顺序。每次划分只使一个子问题缩短一个记录。因此划分的总工作量是一连串逐次变小的线性代价之和,呈二次增长。均匀随机地选取枢轴可以防止该输入排列每次都迫使同样的坏划分,但并不使坏划分不可能发生。
期望时间定理也包含划分所需的工作量。如果实现反复低效地复制记录,或者进行超线性的划分工作,仅仅快速选出枢轴是不够的。所述分析假定对每个子问题做一次线性扫描,且记录与键的操作为常数代价。长字符串、任意精度数或开销高昂的比较函数,需要额外的代价模型。
键相等时需要不同的快速排序分析
精确的逐对公式假定键互不相同,因此每个记录有唯一的名次,且每个枢轴都严格区分较小与较大的键。若所有键都相等,而二路划分把所有非枢轴记录送到同一侧,则即使枢轴是随机的,每次调用也可能只缩小一。枢轴的身份是随机的,但其键没有提供任何平衡信息。键互不相同的定理不能用来宣称这样的执行是高效的。
三路划分把键分为小于、等于和大于枢轴三部分,然后只对严格小于与严格大于的两组递归。这样就在一次线性划分中处理了全部相等的输入。要对任意重复度建立完整的期望界,需要专门的论证;目前的精确公式有意仅限于键互不相同的情形。这个例子指出了缺失的假设,而不是把重复键当作一个微小的实现细节。
反例模式
不稳定的数位排序会破坏先前的工作
取两位数键十二和十一。按个位排序会使十一排在十二之前,它们的十位相同。如果允许十位这一趟颠倒数位相同的记录,就会返回十二在前、十一在后,从而破坏所需的顺序。稳定的最后一趟则保持低位的顺序。仅有数位有序并不能证明一系列基数排序的趟是正确的。
为什么整数排序不违反比较排序下界
比较排序下界描述的是仅通过比较来获知顺序的算法。计数排序读取键值,并用它来选取计数数组中的一项。这是对表示形式的额外访问。即使只出现少数键值,其时间也包含键全集的大小。因此,巨大而稀疏的键全集可能使计数排序比比较排序更差。
基数排序把表示形式的代价分摊到各数位上。其界包含数位个数与进制的大小;它并不是对每一个可能的整数输入都简单地为线性。增大进制会减少数位个数,但会增加每一趟都必须初始化的计数器个数。复杂度论断必须同时保留这两个参数以及数位访问的假设。
概念视角算法
比较界之前先选定模型
插入排序度量的是无序程度,快速排序对内部随机性取平均,计数排序与基数排序则利用键的表示形式。相同的输入长度并不能抹去这些不同的参数。在决定适用哪个定理之前,应当说明键的定义域、重复键的约定、记录移动的代价以及随机性。
常见错误
稳定的算法不一定快,快的算法也不一定稳定。同样,期望界并不是对每个随机种子的保证。对枢轴做随机化,并不会自动使糟糕的重复键处理规则变得高效。
在逆序对分析中,应按原始位置统计键的严格不等式。键相等不产生逆序对。证明所统计的是已有记录的移动次数,而不是包括存放被插入记录在内的所有赋值。额外的放置已计入操作次数界的线性项中。
常见错误
(越过相等的键移动)
当前一个键大于或等于被插入的键时就移动,仍然得到有序的数组,所以看似无害。对 并无逆序对,严格的插入排序不做任何移动;而这种弱比较会把 移动一次,返回 。于是移动次数超过 ,稳定性也随之失去。
常见错误
(把计数排序当作对记录数目是线性的)
其界是 ,只有当键的范围 为 时才对 是线性的。对两个键 与 ,有 而 ,计数排序为了排序两条记录,要初始化并扫描约一百万个计数器。
总结
插入排序每个逆序对花费一次移动,并且在严格移动的条件下是稳定的。随机化快速排序在键互不相同时的期望,源自名次区间端点的概率。计数排序使用有界整数键,其稳定的放置规则支撑了基数排序的归纳。每个界只有连同其输入与运算模型一起才有意义。
练习
快速检查
(计算键 (2a,2b,1a,1b) 中的逆序对个数,并给出插入排序的稳定输出与移动次数。)
下标用于标识记录,不影响其键。
解答 · 答案
键为二的两个记录中,每一个都大于其后键为一的两个记录中的每一个,共得到四个逆序对。键相等的记录对不计入。稳定的插入排序输出 ,并进行四次移动。它还要进行线性的外层循环与放置工作,所以仅移动次数并不是全部的操作次数。
快速检查
(在对 个互不相同的键进行的随机化快速排序中,求最小键与最大键被比较的概率,以及名次相邻的两个键被比较的概率。)
说明为什么这两个答案可能相差很大。
解答 · 答案
对 ,最小与最大名次被比较,当且仅当其中之一是全部 个键中最先被选的枢轴,概率为 。相邻名次构成大小为二的区间,所以其中一个端点必然是该区间中首个被选的枢轴,比较概率为一。居中的名次可以把相距较远的键分开,而对于相邻名次,在其中一个成为枢轴之前,没有任何键能把它们分开。
快速检查
(证明在有序且互不相同的输入上,以第一个记录为枢轴且划分保持相对顺序时恰用 次比较。解释这为什么与随机化的期望定理并不矛盾。)
写出划分比较次数之和,并指出被改变的假设。
解答 · 答案
保持相对顺序的划分使每个递归子问题仍然有序,所以其第一个记录总是最小的键。各次划分的规模为 ,分别贡献 次比较。它们的和为 ,当 时为零。这个枢轴规则是确定性的,而不是在每个子问题内均匀选取。即使是随机化算法也可能产生同样的序列,但其定理是对所有枢轴选择取平均,而不是用期望来界定每一次执行。