《chapter2 Sortin算法和算法的分析技术》由会员分享，可在线阅读，更多相关《chapter2 Sortin算法和算法的分析技术（80页珍藏版）》请在金锄头文库上搜索。
1、计算机算法计算机算法设计与分析导论设计与分析导论南开大学南开大学 计算机科学与技术系计算机科学与技术系刘璟迄搁文哗焊鄙楚堡守涣雏舀片么痴邦科柑禹牡凯讼仗亡肘酞葫觅超篙缨走chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术1Chapter 2. Sorting算法与算法的算法与算法的分析技术分析技术 v 2.1 排序排序(Sorting)问题问题 v 2.2 O(n2)阶的排序算法阶的排序算法 v 2.3 基于相邻元比较的排序算法和希尔基于相邻元比较的排序算法和希尔(Shell)排序排序 v 2.4 O(nlogn)阶的排序算法阶的排序算法 v
2、2.5 比较排序算法的时间复杂度下界比较排序算法的时间复杂度下界 v 2.6 排序算法的有关研究排序算法的有关研究 苟贬现雕敞助宦旦控蛊氧剖再胯闰浇迭哄隶磁硼安紫煎撰杭奄依守尾放捍chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术22.1 排序（排序（Sorting）问题）问题 有关排序的几个基本概念：有关排序的几个基本概念：1. 全序集：全序集：数据集合数据集合D称为关于关系称为关于关系“”的全序集，如果的全序集，如果 满足满足 1 a b，a = b，b a 三者必居其一；三者必居其一； 2 a b，b c，则，则a c。全体整数集、实数集
3、、字符串集等都是全序集。全体整数集、实数集、字符串集等都是全序集。 2. 排序（排序（Sorting）问题：）问题：已已知知：n项项记记录录R1，R2，Rn，其其一一个个域域称称为为关关键键字字（Key），关键字值），关键字值K1，K2，Kn属于一全序集。属于一全序集。要要求求：重重排排n项项记记录录为为R(1) ，R(2)，R(n)，其其中中：(1)，(2)，(n)，为为1, , n的的一一个个排排列列，使使对对应应的的关关键键字字满满足足：K(1) K(2) K(n)。芜芯辞世买摇用屡惠挝趣糜戴诧击矾琼辆獭韶流宣婉陆蹬栽乳蠕坊繁斤苍chapter2 Sortin算法和算法的分析技术chap
4、ter2 Sortin算法和算法的分析技术33. 稳定（稳定（Stable）排序算法：）排序算法：如如果果排排序序问问题题满满足足：若若R(i) = R(j) 且且 i j 则则(i) (j )，则则称称其其为为稳稳定定排排序序算算法法。稳稳定定排排序序保保证证序序列列中中关关键键字字相相同同的的记记录录在排序过程中不会交换次序。在排序过程中不会交换次序。4. 内部（内部（Internal）排序算法：）排序算法：数数据据在在高高速速随随机机存存储储设设备备上上（内内存存）进进行行排排序序操操作作，这这时时数数据间的比较和移动指令的代价一般是相同的。据间的比较和移动指令的代价一般是相同的。5.
5、外部（外部（External）排序算法：）排序算法：数数据据主主要要驻驻留留在在外外部部的的低低速速存存储储设设备备（硬硬盘盘、磁磁带带）上上，数数据据在在内内存存与与硬硬盘盘（磁磁带带）之之间间的的传传送送、移移动动的的代代价价明明显显高高于于数据比较操作，因此，外部排序算法的设计不同于内部排序。数据比较操作，因此，外部排序算法的设计不同于内部排序。蒜困寨撕氨扁感虾妈条败蓬镐瞪兴冠液互僚军誊攀亡泥明特蛋钮敦掖案轮chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术46. 原址排序算法：原址排序算法：在在排排序序过过程程中中除除了了全全部部输输入
6、入数数据据所所占占用用的的空空间间之之外外，只只需需有有限限的的额额外外空空间间。如如果果额额外外空空间间的的大大小小与与记记录录数数n无无关关，则则称称为为原址排序。原址排序。7. 基于关键字比较的排序算法：基于关键字比较的排序算法：这类排序算法中仅对关键字进行比较和移动操作，因此关键这类排序算法中仅对关键字进行比较和移动操作，因此关键字的比较和移动是算法的基本操作。字的比较和移动是算法的基本操作。丈样告穴垮放穿辰杆挣洼免透玉虐炙符慕痴妈齿钙之乍迷滓荚鸭窄更腰诺chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术52.2 O(n2)阶的排序算法
7、阶的排序算法 v2.2.1 选择排序（选择排序（Selection Sorting） 1. 选择排序的思想：选择排序的思想：把待排序的把待排序的L1. n视为两个部分：视为两个部分： L1.i- -1为已排序部分，为已排序部分，L i .n 为未排序部分。排序步骤为：为未排序部分。排序步骤为： 1 i = 1；2 选择：在选择：在L i.n 中求最小元中求最小元Lk，i k n；3 交换交换Li与与Lk，i+，if（ i Lj的执行次数。另外，函数的执行次数。另外，函数Swap( )需要需要3次次移动，共移动，共3( n 1 )次。因此，选择排序算法的平均移动次数会次。因此，选择排序算法的平均
8、移动次数会比较小，而最好情形则为比较小，而最好情形则为3( n 1 )。当数据记录比较大时，移。当数据记录比较大时，移动代价大于比较代价，选择排序也可能有较好的性能。动代价大于比较代价，选择排序也可能有较好的性能。 衡咨料市竭蜀瑶用鞠喷絮囊蘸擅汐亥哎鹰纹丽瞻所猿炮宿谤驼堂诽谋壹投chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术8v2.2.2 插入排序（插入排序（Insertion Sorting） 1. 插入排序的思路：插入排序的思路： 与选择排序不同，它是从无序部分不经选择，任取一元，然与选择排序不同，它是从无序部分不经选择，任取一元，然后
9、插入到有序部分的正确位置上。后插入到有序部分的正确位置上。其步骤为：其步骤为：L 1.n 分分为为两两部部分分：L 1.i 为为有有序序部部分分，L i+1.n 为为未未排排序序部分。部分。 1 i = 1 ； 2 把把Li+1插入到插入到L1.i中的正确位置，中的正确位置，i+； 3 if ( i n ) goto 2； 4 停止。停止。2. 算法的描述：算法的描述： 算法算法 2.2 插入排序算法插入排序算法 InsertSort 肺场痰厅丢宠馋际秒斤糠疾斩深军耿蔓抢犬甫娃别筐碎隅账观窥遏惩酋瘸chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析
10、技术93. 算法的分析：算法的分析：最坏情形：最坏情形：最好情形：最好情形：平均情形：设输入序列满足两个条件：平均情形：设输入序列满足两个条件：1 n个关键字值是不同的，这可以简化分析；个关键字值是不同的，这可以简化分析；2 n个元素的所有不同的排列具有等可能性。个元素的所有不同的排列具有等可能性。在把在把Li插入到有序的插入到有序的L1.i1的过程中，共有的过程中，共有i种可能的位置，种可能的位置，由假设由假设2可知落入每个位置的概率为可知落入每个位置的概率为1/i。而这。而这i种情形所需要种情形所需要的比较次数分别为的比较次数分别为1，2， ，i-2，i-1，i-1，因此期望的比较，因此期
11、望的比较次数为：次数为：蕾央答塞草休钢孺停爽淳妓窖一痈鞭了啪惧念饱萤艇囤验溜荣穿荒伦拙差chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术10因此，因此， 插入排序虽然也是插入排序虽然也是O(n2)阶的算法，但在一般情形下，会比选阶的算法，但在一般情形下，会比选择排序块。择排序块。算法的空间代价：基本上不需要额外空间，也是一种原址排算法的空间代价：基本上不需要额外空间，也是一种原址排序算法。序算法。它也是稳定的。它也是稳定的。钳歌本俊尿肠练毯靖莲写诧剿秉瑚雁抓觅遗怯咳兼魔丧食稿欲澳疵乐磺拓chapter2 Sortin算法和算法的分析技术cha
12、pter2 Sortin算法和算法的分析技术114. 讨论：讨论： 在基于相邻元比较交换的排序算法中，在基于相邻元比较交换的排序算法中，InsertSort是最优的。是最优的。如如果果把把数数据据的的移移动动作作为为基基本本操操作作，每每一一次次数数据据比比较较都都有有一一次次数数据据移移动动与与之之对对应应。因因此此，除除了了在在外外循循环环的的n 1次次移移动动之之外外，数据比较与移动次数是一致的，这与数据比较与移动次数是一致的，这与SelectSort算法是不同的。算法是不同的。v2.2.3 起泡排序（起泡排序（Bubble Sorting） 算法算法 2.3 起泡排序算法起泡排序算法
13、BubbleSort 算法算法BubbleSort的比较次数是确定的：的比较次数是确定的：移移动动次次数数与与数数据据比比较较相相对对应应，交交换换函函数数Swap需需要要三三次次数数据据移移动动，在在最最坏坏情情形形下下是是比比较较次次数数的的三三倍倍，而而在在最最好好情情形形下下不不需需要移动。要移动。澳撑瞳傈述唐泳己旋绩太孝搏眯症糊隋坍赘颊戏昌官藐碑渭崔遇僻桔弱稗chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术12BubbleSort是稳定的、原址排序算法。是稳定的、原址排序算法。BubbleSort的的一一种种实实用用改改进进算算法法
14、是是在在程程序序中中设设一一标标记记位位，当当一一遍扫描中没有交换发生，则排序停止。遍扫描中没有交换发生，则排序停止。 算法算法 2.4 起泡排序的改进算法起泡排序的改进算法 BSort 算法算法BSort的比较次数有所改进：的比较次数有所改进： 舒摊潜挥随煌憋嗡茹骂果遥鸯趋锗挣谷叫永敷叶让救忆惑蚌敛泪裔茧敲取chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术132.3 基于相邻元比较的排序算法和基于相邻元比较的排序算法和希尔（希尔（ShellShell）排序）排序 v2.3.1 插入排序的最优性插入排序的最优性 定理定理2.1 基于相邻元的比
15、较及交换的排序算法基于相邻元的比较及交换的排序算法 1在最坏情形下，至少需要在最坏情形下，至少需要n(n-1)/2次比较，即次比较，即W(n) = (n2)； 2在平均情形下，至少需要在平均情形下，至少需要n(n-1)/4次比较，即次比较，即A(n) = (n2)。把把n个个元元素素排排列列问问题题归归结结为为以以n个个关关键键字字1, 2, ,n的的任任一一排排列列：(1), (2), ,(n)作作为为输输入入，排排序序过过程程就就是是消消灭灭序序列列中中的的逆逆序的过程。序的过程。所所谓谓逆逆序序（Inversion）（(i), (j) ），即即i (j)。例例如如序序列列（2，4，1，5
16、，3）有有4个个逆逆序序：（2，1），（4，1），（4，3），（），（5，3）；）；撤费病具劳视鹰哪锚频氯觉坟疙慷沫兜怪迎整纸乍虾压椭企横剔一轿显徊chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术14证证明明的的关关键键是是，在在序序列列中中，如如果果两两个个相相邻邻元元为为一一逆逆序序，经经过过交换肯定消除了这个逆序，但这一交换只能消灭这一个逆序。交换肯定消除了这个逆序，但这一交换只能消灭这一个逆序。证明：证明：1存存在在一一种种排排列列：n, n-1, ,2, 1 为为全全逆逆序序，共共包包含含n(n-1)/2个个逆逆序序，故故在在最最坏
17、坏情情形形，任任一一依依靠靠相相邻邻元元比比较较、交交换换完完成成的的排排序过程，至少需序过程，至少需n(n-1)/2次比较，即次比较，即W(n) = (n2)。2对对于于平平均均情情形形，实实际际上上需需要要计计算算1, 2, ,n的的所所有有不不同同排排列列的的平均逆序数。平均逆序数。当当n 1时，任一排列时，任一排列，必有一个唯一的、不同于它的对偶排列；，必有一个唯一的、不同于它的对偶排列；是是的对偶排列，即的对偶排列，即是是的反序：的反序：(1)= (n)，(2)= (n-1), , (n)= (1)，例例如如，(2,4,1,5,3)的的对对偶偶排排列列是是(3,5,1,4,2)； 1
18、n之之间间的的任任一一整整数数对对（i, j）（ij）如如果果是是逆逆序序，必必然然出出现现在在任任一一排排列列及其对偶排列及其对偶排列二者之一；二者之一；惶挎者亨寿望授掩脊翻咆唯豁昌衫魁粮畦百撩刹碑新淳尽颇懂倾思卢群崩chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术15 1n之间共有不同的整数对（之间共有不同的整数对（i, j） n(n-1)/2个；个； 1, ,n的的所所有有排排列列是是成成对对出出现现的的，故故每每一一排排列列平平均均有有n(n-1)/4个个逆逆序序，平平均至少需均至少需n(n-1)/4次比较，即次比较，即A(n) =
19、(n2)。 由定理知：由定理知：1算法算法InsertSort和和BSort在上述条件下是最优的；在上述条件下是最优的；2为为了了设设计计比比(n2)阶阶更更快快的的排排序序算算法法，数数据据的的比比较较和和移移动动必必须在间隔较大的元素之间进行。须在间隔较大的元素之间进行。v2.3.2 希尔（希尔（Shell）排序）排序 该排序算法首先把输入序列分成该排序算法首先把输入序列分成h个间距为个间距为h的子序列，对每的子序列，对每个子序列进行个子序列进行hsorting。例如，取。例如，取h = 6，则，则L1.n分为分为6个子个子序列：序列：哥牌抱倾许昧欺瑚替溶微屑蜀蹭稻蚊滇乍锈航莉屏矢掸庇莉汕
20、瞥辗统膀菩chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术16L1, L7, L13, L2, L8, L14, L3, L9, L15, L4, L10, L16, L5, L11, L17, L6, L12, L18, 进进行行hsorting后后，就就是是逐逐步步减减少少h的的大大小小，直直至至把把h减减少少到到1，完完成成排排序序工工作作。在在最最后后一一次次h = 1时时，采采用用InsertSort或或BSort算算法法，可可能能出出现现最最好好情情形形或或几几乎乎最最好好情情形形，而而InsertSort的的B(n)=n-1，故
21、故总总比比较较次次数数有有望望缩缩小小。Shell排排序序算算法法有有几几个个因因素素可可以以有有大大的的变化化：第第一一个个h值如如何何取取，h值如如何何逐逐步步减减少少到到1每次每次hsorting采用何种算法，都采用何种算法，都对整个算法性能有大的影响整个算法性能有大的影响。铂蛤顺尝戮铬峦汕烃速怎啼存底吱加互灰被匡疗坷粪退壤谩伏钳老晰惭财chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术17Shell排序算法：排序算法：输入：输入：Key L1.n：关键字数组；：关键字数组；int h1.t：递增整数序列，：递增整数序列，h1 = 1；算
22、法算法 2.5 希尔排序算法希尔排序算法 ShellSort 当当t = 1时，时，ShellSort退化为退化为InsertSort。增量序列。增量序列ht, ht-1, h1 = 1应事先确定，一个较好的选择是：应事先确定，一个较好的选择是：h1 = 1, hs+1 = 3hs + 1其中其中1st 使使ht+1 1时，时，在在h-sort过程中，一次比较和交换可以至多消除过程中，一次比较和交换可以至多消除2ht -3个逆序。个逆序。关于关于Shell排序的研究至今仍在继续，因为对于已知的排序的研究至今仍在继续，因为对于已知的n，怎样，怎样的增量的增量h序列使算法性能最佳，其最优时间复杂度
23、如何，目前序列使算法性能最佳，其最优时间复杂度如何，目前尚不清楚。一些比较好的成果指出，适当选取增量序列，尚不清楚。一些比较好的成果指出，适当选取增量序列，Shell排序算法的复杂度可以达到排序算法的复杂度可以达到O(nlog2n)和和O(n1.25)。 班乔藩旧锐堆呐氖邹众羌纠颅从湃削浸家忱盒枝烤楔盛志置攀绣己芝纂圆chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术182.4 O(nlogn)阶的排序算法阶的排序算法 v2.4.1 快速排序算法快速排序算法QuickSort 1. 算法的思路：算法的思路： 其关键操作是其关键操作是划分划分（p
24、artition）：）：取取n元中的任一元（例如首元）作为划分元（元中的任一元（例如首元）作为划分元（pivot），令其余），令其余n 1个元与划分元经过比较，把较小者移至划分元左边，而个元与划分元经过比较，把较小者移至划分元左边，而较大者置于划分元之右，形成两个序列。左序列的所有元都较大者置于划分元之右，形成两个序列。左序列的所有元都小于划分元，右序列都不小于划分元，然后用同样的方法对小于划分元，右序列都不小于划分元，然后用同样的方法对左、右序列排序，从而完成排序目标。如左、右序列排序，从而完成排序目标。如Fig.2.1 所示。所示。划分过程中，划分元被放置到了排序过程的最终位置，其左、划分
25、过程中，划分元被放置到了排序过程的最终位置，其左、右两个序列虽然是无序的，但作为整体却被确定了位置，因右两个序列虽然是无序的，但作为整体却被确定了位置，因此在完成左、右子序列的排序之后，整个排序过程也就完成。此在完成左、右子序列的排序之后，整个排序过程也就完成。咬哗键蚜坪虫诽楔膨遮彪巷禽朵叉吗憋准曝瞒宰欲呸豌楚浙筑锭惶泥蝎猴chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术19细寺滦批溃颂灶鉴犹扫需鹰索癌抽挫讥都峙棺慢圾尖短蹲狭贸堡巨试蒙逸chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术202
26、. 算法算法QuickSort： 输输入入：未未排排序序的的L1.n，为为了了方方便便写写递递归归程程序序可可表表示示为为Lfirst.last。输出：输出：已排序的已排序的Lfirst.last。算法算法 2.6 快速排序算法快速排序算法 QuickSort3. 划分算法划分算法Partition： QuickSort的核心是的核心是Partition。划分过程中，元素在数组中有。划分过程中，元素在数组中有较大幅度的移动，因此，这也是快速排序速度较快的内在原较大幅度的移动，因此，这也是快速排序速度较快的内在原因。因。有各种不同的划分算法，其性能也不尽相同。一种较好的划有各种不同的划分算法，其
27、性能也不尽相同。一种较好的划分算法，其思想如分算法，其思想如Fig.2.2所示。所示。 怎凋盛中功软蔓威握招族棘艾战锑常摧捌偶挟然辞堑婆葬削穆十疲矣尺显chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术21肿祟樟撂坞愉述烹圃坤影砰罪蜒凉铲弥痢喷林箍朵馒眠忙仔虹熟谗笑涅毕chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术22程序开始，指针程序开始，指针left = first，指向空位，即划分元，指向空位，即划分元pivot的位置，的位置，指针指针right = last，指向最右元，序列，指向最
28、右元，序列L2.n全为未做划分处理全为未做划分处理部分；首先自部分；首先自right开始，向左扫描，找到第一个小于开始，向左扫描，找到第一个小于pivot的的元素，把它送往元素，把它送往left指向的左空位，指向的左空位，left右移一位；然后从右移一位；然后从left向右扫描，找到第一个不小于向右扫描，找到第一个不小于pivot的元素，把它送到的元素，把它送到right指指向的位置（右空位），向的位置（右空位），right左移一位，完成划分的一次循环。左移一位，完成划分的一次循环。重复上述循环，直到重复上述循环，直到left = right，令，令Lleft = pivot，返回，返回lef
29、t。算法算法2.7 快速排序的划分算法快速排序的划分算法 Partition铁龚乱红筹现组鸡堪澳挥随暂遮耘布会孜糖伏胁辽蜘蟹辱世赞覆幌额寝鱼chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术23划分过程中的实例：划分过程中的实例： 闲壕徐军证譬锤项雁庄啼据蚂沟鼓刊煎仕邢理棱倔超常塘最输爪帝癣骗唾chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术244. QuickSort的复杂度分析：的复杂度分析： 最坏情形最坏情形的总比较次数为：的总比较次数为：平均时间性能分析平均时间性能分析：首先假设：首先
30、假设：1n个元素的关键字值互不相等。个元素的关键字值互不相等。2n个元素的关键字的所有不同排列，以等可能即相等的概率出现在输入个元素的关键字的所有不同排列，以等可能即相等的概率出现在输入序列中，因此，划分元的最终位置序列中，因此，划分元的最终位置i也以相等概率分别取值为也以相等概率分别取值为1, ,n。QuickSort的平均比较次数的平均比较次数A(n)应满足递归方程：应满足递归方程： 嗜夏强傲槐危疚屏檀聂垦秘拓汲善汉珠罐姐僚拒俏蛀梯蚕幻瑞腑粘伞办挑chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术25可简化为：可简化为： （公式（公式2.4
31、.1） 在最好情形时划分元总是处于序列的中间，递归方程可大致在最好情形时划分元总是处于序列的中间，递归方程可大致简化成：简化成：晕沧瑚阿维盆政砷俞弹呆色篇汰采坑这仆迎慨没窍际幅乞淳试悉漾鞍隔掷chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术26定理定理2.2 在输入序列的所有排列具有等可能性的条件下，算法在输入序列的所有排列具有等可能性的条件下，算法QuickSort的平均数据比较次数为的平均数据比较次数为: 其中其中c 0为一常数。为一常数。证明方法证明方法1：采用归纳法采用归纳法 当当n = 1时，时， A(n) = 0，cn lnn =
32、 0，命题成立；，命题成立；假设当假设当1 k n， A(K) ck lnk 成立；成立； 由公式由公式2.4.1和假设得：和假设得： 根据积分的性质：根据积分的性质：威逊涟隅件祟化鞋娱瞥姬夷砸声吹肇脊谓塞钠琢搬寅歪掉荷借班邓减砒扫chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术27于是，当于是，当n1取取c = 2时，时， A(n) 2n lnn 成立。成立。推论推论2.3 在在输入序列的不同排序均匀分布的假入序列的不同排序均匀分布的假设条件下，算法条件下，算法QuickSort的平均数据比的平均数据比较次数次数为: 证明方法证明方法2：为
33、了了简化关于化关于A(n)的的递归方程，方程，由由 博模肯镍函跟辈狞嚣系盅褐恭矾少姚网申龄晦究栋僻声樟促等涤样峡济贿chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术28推出：推出：为了消除过多的为了消除过多的A(i)项，计算项，计算nA(n)-(n-1)A(n-1) ：即即令令 则有：则有：划斧棋脓僧衍京氨练讣煤战些招拯健毕尤蜒看肖铸葡锋遮莹二发各纪希颠chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术29这是一个较为简单的递归方程，不难得到：这是一个较为简单的递归方程，不难得到：由由Harm
34、onic级数，数， 为Euler常数，常数， ，得：得：叙球肛进摇盟践途缘瓶掣窑捡给个离踊跺跃牧机府腻撕服浦骂浦滓坡科贴chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术30 由此可以得到由此可以得到A(n)的更准确的表达式：的更准确的表达式：5. 空间复杂度分析：空间复杂度分析： 单从划分算法来看，单从划分算法来看，QuickSort除有限的工作单元外，不占用除有限的工作单元外，不占用额外的空间，但在递归过程中，待排序段的首元和尾元下标额外的空间，但在递归过程中，待排序段的首元和尾元下标需要保存，在最坏情形可能递归需要保存，在最坏情形可能递归
35、n 1次。因此，次。因此，QuickSort在在最坏情形下需要的空间代价为最坏情形下需要的空间代价为S(n)=(n)。 青扭巍镭硕碑变呢儿偷抉建藤土委拄够起愤帽屈业先藕秉肥氏清酵急骇延chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术316. 关于关于QuickSort算法的几点讨论：算法的几点讨论： 1）在最重要的性能，即平均时间代价上优于其它算法。在最重要的性能，即平均时间代价上优于其它算法。当当n比较大时，一般运行确实很快，因此被广泛采用。比较大时，一般运行确实很快，因此被广泛采用。2）改善划分元的选取，可能产生更好的效果。常见的几种划改
36、善划分元的选取，可能产生更好的效果。常见的几种划分元的选取方法是：分元的选取方法是： 在在first, ,last中取随机数中取随机数i，以，以Li 代替代替L1； 在在first, ,last中，取中间值中，取中间值i = int (first+last)/2)； 取取first，last，int（first+last）/2）三者的中值为划分元下标。）三者的中值为划分元下标。3）算法的核心是划分。不同的划分策略会影响到移动次数。算法的核心是划分。不同的划分策略会影响到移动次数。 4）QuickSort采用递归算法的形式，简明但运行时在时间和采用递归算法的形式，简明但运行时在时间和空间上开销较
37、大。一种改进方法是使用由用户设计的栈取代空间上开销较大。一种改进方法是使用由用户设计的栈取代递归。递归。 算法算法2.8 快速排序的改进算法快速排序的改进算法 QStackSort 函枣多老磷赡赚患餐茧忠规孙你娇匝道周撵疵柒拽掖痛罚措韦晴圆部垛惮chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术325）空间复杂度的改进：空间复杂度的改进：快速排序算法的额外空间需求与递归和栈有关。当把两次递快速排序算法的额外空间需求与递归和栈有关。当把两次递归调用改为单侧进栈，可以改进空间复杂度。当输入为升序归调用改为单侧进栈，可以改进空间复杂度。当输入为升序（
38、已排序）时，共需（已排序）时，共需n 1次进栈，占用次进栈，占用O(n)空间。如果在程空间。如果在程序中，每进行一次划分以后，就对序中，每进行一次划分以后，就对 f, i-1 , i+1,l 两段进行比两段进行比较，把较大的一半进栈，先计算（划分）较小的一半，其内较，把较大的一半进栈，先计算（划分）较小的一半，其内层循环次数（即栈的长度）必然小于层循环次数（即栈的长度）必然小于logn，因此空间代价可降，因此空间代价可降为为O(logn)。 6）快速排序算法对于较小的快速排序算法对于较小的n，其性能不及插入算法。因此，其性能不及插入算法。因此，可以设计一种综合算法，当输入序列长度小于某个固定值
39、可以设计一种综合算法，当输入序列长度小于某个固定值（例如（例如 n0=50）时，改用）时，改用InsertSort进行排序。进行排序。7）快速排序的最坏情形时间复杂度和额外空间代价，无论如快速排序的最坏情形时间复杂度和额外空间代价，无论如何改进，总是它的缺点和不足。何改进，总是它的缺点和不足。尸罐掇瞎均构虐椅辰目斧为未炭碗格企梨蜘币柜令芯哥贾柜奉哉经欲仗闹chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术33v2.4.2 合并排序算法合并排序算法MergeSort 1. 算法的思路算法的思路 ： 把序列分为两部分，分别递归（排序）后，再把两个有
40、序序把序列分为两部分，分别递归（排序）后，再把两个有序序列合并为一个有序序列。如列合并为一个有序序列。如Fig.2.4。 湍剔苇宁湖陈所皇作氨屏隋逐匡法辱津成戎装卜遣驮尤烟做铝芭她琐梧胁chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术342. 有序序列的合并算法：有序序列的合并算法： 算法算法2.9 有序序列的合并算法有序序列的合并算法 Merge 3. 合并排序算法合并排序算法MergeSort： 算法算法2.10 合并排序算法合并排序算法 MergeSort 4. 算法的复杂度分析：算法的复杂度分析： 该算法对两个长度为该算法对两个长度为
41、m的有序序列的合并，在最坏情形下至少的有序序列的合并，在最坏情形下至少需要需要2m 1次比较。次比较。算法在最坏情形下的比较次数可用递归方程表示：算法在最坏情形下的比较次数可用递归方程表示： （公式（公式 2.4.2） 靠绊羊讶纂纯蜗着助租摧件毅哇萤琅燎掀脓躯日鬃贯沙坠侦帅虫埃债档鹏chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术35忽略忽略n为奇数的情形，由主项定理可得为奇数的情形，由主项定理可得 。 假定假定n = 2k（k为正整数），则公式为正整数），则公式2.4.2可以简化为：可以简化为： 直接推导得：直接推导得： 该算法平均情形比较
42、次数该算法平均情形比较次数A(n) =(nlogn)。其空间代价较大，需要大小为其空间代价较大，需要大小为O(n)的额外空间。的额外空间。该算法是不稳定的。该算法是不稳定的。冷恿速吁浚从殊伪苍少帝搪鸡肯瓷亚癌费匣呐郡垒衷尘洪沧区碗耙陛改销chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术365. 关于合并排序算法的讨论：关于合并排序算法的讨论： 1）对于时间复杂度而言，在最坏情形下大大优于快速排序，对于时间复杂度而言，在最坏情形下大大优于快速排序，但在平均情况下不一定优于快速排序。数据的移动次数也会但在平均情况下不一定优于快速排序。数据的移动次
43、数也会对时间性能有所影响。对时间性能有所影响。 2）可以比较容易地改写成非递归程序。可以比较容易地改写成非递归程序。3）合并排序的一种改进方法是充分利用输入序列中可能的已合并排序的一种改进方法是充分利用输入序列中可能的已排序部分。排序部分。 算法算法2.11 合并排序改进算法合并排序改进算法II MergeSort2 例如，输入序列为（例如，输入序列为（4，12，8，6，0，11，27，5，20），实），实际上是际上是4个有序串：（个有序串：（4，12），（），（8），（），（6，11，27），），（5，20）。第一趟扫描合并为：（）。第一趟扫描合并为：（4，8，12），（），（5，6，9，1
44、1，20，27），第二趟扫描就已排好序。），第二趟扫描就已排好序。 这个算法在在最好情形下的比较次数为这个算法在在最好情形下的比较次数为B(n) = n 1。封闹姆侩备斧阀块支沽竟雪厩墓厚发和鹿毖校炕爬蛙区蹈十妒区疑釜同挪chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术374）主要缺点是空间代价较大，每次合并操作都需要与待合并主要缺点是空间代价较大，每次合并操作都需要与待合并的数据等长的额外空间，其额外空间代价为的数据等长的额外空间，其额外空间代价为O(n)阶。阶。 5）适合于并行计算。适合于并行计算。v2.4.3 堆排序算法堆排序算法Hea
45、pSort 1. 堆排序算法的思路：堆排序算法的思路： 如如Fig.2.5，算法把待排序的，算法把待排序的数组数组L1.n视为一个二叉树，视为一个二叉树，数组元素依次按广度第一的数组元素依次按广度第一的顺序与二叉树的结点相对应。顺序与二叉树的结点相对应。结点间的链接利用下标来计结点间的链接利用下标来计算。对于结点算。对于结点i，如果，如果2i n，则，则i为叶结点，否则，为叶结点，否则，2i为为其左儿子下标，其左儿子下标，2i+1为其右为其右儿子下标。儿子下标。 膊义犬吞撼吱滔句凶怠筏翼友控讳己吐河向件拇愈醚改残化仔祝激血委对chapter2 Sortin算法和算法的分析技术chapter2
46、Sortin算法和算法的分析技术38这样的二叉树的所有的叶结点位于树的最底层即这样的二叉树的所有的叶结点位于树的最底层即d层或层或d 1层，层，在最底层的叶结点位于左端。在最底层的叶结点位于左端。算法由两部分组成，第一部分称为算法由两部分组成，第一部分称为建堆建堆（BuildingHeap），），就是通过数据的比较和移动，使得二叉树上每个内部节点的就是通过数据的比较和移动，使得二叉树上每个内部节点的值大于其左、右子结点的值。这样的二叉树称为堆（值大于其左、右子结点的值。这样的二叉树称为堆（Heap），），如如Fig.2.6所示。所示。 俞搅割争涵谬饿侥弧碾廉坏痉告钡孤笨搽敷陡屏玉雹胰烫墟擅寸阔
47、坐瘸预chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术39第二部分称为第二部分称为根删除根删除堆修复堆修复（Delete Fix）过程，如）过程，如Fig.2.7，可以描述为：，可以描述为： for ( i = n ; i = 2 ; i- ) Swap( L1 , Li ) ; FixHeap( L1.i-1 );堆的修复过程，就是每次把两个儿子中的较大者上升，直到堆的修复过程，就是每次把两个儿子中的较大者上升，直到元素元素Li降到适当的位置为止。这一降到适当的位置为止。这一Delete Fix过程至多重复过程至多重复n次，每次修复所需的比
48、较次数不会大于树高，而平衡二叉树次，每次修复所需的比较次数不会大于树高，而平衡二叉树的高不会大于的高不会大于logn（n为结点数），故此算法应有较好的性能。为结点数），故此算法应有较好的性能。 2. 算法的描述：算法的描述： 算法算法2.12 堆排序算法堆排序算法 HeapSort 赢诊延啡押龚谷仿眷敝老锑妇咖颖擅榴拄长瓢慌勇丹宁折褥读膳拦捎东培chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术40锐逝录涣跪虎让虐信岛岂法钢骂坤鞍叶突揩泡焦平糙夕退惕指撮手扼刑粘chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法
49、和算法的分析技术413. 算法的分析算法的分析 ： 令令n = 2d 1 且且 n/2 n n ，并把建堆过程写成递归形式，并把建堆过程写成递归形式 ：void BHeap( H ) BHeap( Hleft ) ; BHeap( Hright) ; FixHeap( L , n , root , Lroot ) ; return ;它与函数它与函数BuildHeap是等价的。是等价的。由于由于FixHeap( L, n, root, Lroot )的比较次数为的比较次数为2logn，故有：，故有： 椰赌筛镶蚁战货壁锨锄几汾贷软辙洋侥蛮虑镣盛酝茧瞄耪城君屹赵哼甥纬chapter2 Sortin
50、算法和算法的分析技术chapter2 Sortin算法和算法的分析技术42根据主项定理：因为根据主项定理：因为b = 2，c = 2，取，取= 0.1，有，有 故故 因此，建堆过程在最坏情形下的时间复杂度为线性阶。因此，建堆过程在最坏情形下的时间复杂度为线性阶。对于算法的第二部分，因为对于有对于算法的第二部分，因为对于有k个结点的堆进行修复，至个结点的堆进行修复，至多需要多需要 次比较，即全部比较次数至多为：次比较，即全部比较次数至多为： 师遵俩睹鬃唤戒豢埋慌迫牧鸟磅惰雁恒泻凶剿垮犁套捍瑚逢嗣筛袍镭彻傅chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的
51、分析技术43定理定理2.4 HeapSort在最坏情形下的数据比较次数为在最坏情形下的数据比较次数为W(n) = 2nlogn + O(n)，即，即HeapSort是一个是一个(nlogn)阶的排序算法。阶的排序算法。HeapSort在平均情形下的比较次数是在平均情形下的比较次数是O(nlogn)。它是一个原。它是一个原址排序算法。址排序算法。 4. 堆排序算法的缺点：堆排序算法的缺点： 1）当输入序列为有序或几乎有序时，堆排序算法根本没有利当输入序列为有序或几乎有序时，堆排序算法根本没有利用序列有序的条件，需要用序列有序的条件，需要(nlogn)次比较，与最坏情形相比次比较，与最坏情形相比几
52、乎没有改进。几乎没有改进。2）堆排序大约需要堆排序大约需要2 * nlogn次比较，在大多数情况下，比快次比较，在大多数情况下，比快速排序和合并排序要慢。速排序和合并排序要慢。 5. 加速堆排序算法加速堆排序算法AHeapSort： 在原来的在原来的FixHeap算法中，每一次需要做两次比较，即：算法中，每一次需要做两次比较，即：if( Lvac*2 Lvac*2+1 )和和if( k Llarger )。改进后的。改进后的AFixHeap算法，每一步只做一次比较。算法，每一步只做一次比较。沃陛寓孽蓬钻族慎庆煞僻棒苍统跺经糯篆炮桓兰候卷洪滋坠赛殊女泼痪碗chapter2 Sortin算法和算法
53、的分析技术chapter2 Sortin算法和算法的分析技术44算法算法2.13 改进的堆恢复过程改进的堆恢复过程 AfixHeap 在大多数情况下，第一个循环把空位移至叶结点，共用在大多数情况下，第一个循环把空位移至叶结点，共用logn次次比较，而向上的移动次数则很少。结点的比较次数在最坏情比较，而向上的移动次数则很少。结点的比较次数在最坏情形下仍为形下仍为2logn，但在大多数情况下则接近（大于），但在大多数情况下则接近（大于）logn。如。如Fig.2.9所示。所示。 榴茧闲魁呐泻携墓机羔桐恼呕瞧摈知铺姥耐姿础畏蹬移删忱触猜芥剐轧肇chapter2 Sortin算法和算法的分析技术cha
54、pter2 Sortin算法和算法的分析技术45为了把最坏情形下的比较次数由为了把最坏情形下的比较次数由2nlogn缩小到缩小到nlogn，进一步，进一步改进的思路描述如下：改进的思路描述如下：设堆的高度为设堆的高度为 ，空位的移动分为下移和上移，每下移、上移一层需要一次比空位的移动分为下移和上移，每下移、上移一层需要一次比较。开始时空位在顶点，设待插入元素的最终应插入的位置较。开始时空位在顶点，设待插入元素的最终应插入的位置在在h层，层，0hH。1m = H/2；2空位下移空位下移m层，共用层，共用m次比较；次比较；3if( Lvac/2 n!。 仑流蟹蜡阴泉键持屯忌恭菲迪吐坛绥猫妇饱姜嘘轩
55、帘支尖巳净狡昆辖磨拎chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术59引理引理2.9 在所有具有在所有具有l个叶结点的判定树中，若某棵树的个叶结点的判定树中，若某棵树的epl最最小，则这个小，则这个DT的所有叶结点是平衡的，即它的叶结点之多分的所有叶结点是平衡的，即它的叶结点之多分布在树的最下面两层。如布在树的最下面两层。如Fig.2.14。证明：证明： 设判定树有叶结点设判定树有叶结点X位于位于k层，层，k d 1。因。因DT有有d层，故必层，故必有叶结点有叶结点Z1，Z2在在d层，其父结点层，其父结点Y在在d 1层。层。 格啥伍裴荡忍憾
56、助倪保暮莱雾育氦情经妥喷荚二划蜀挡筹橡啄儿律蛮以联chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术60对判定树对判定树DT做一小的调整，把叶结点做一小的调整，把叶结点Z1，Z2从父结点从父结点Y上摘上摘下，挂到结点下，挂到结点X上（如上（如Fig.2.15）。显然它仍然是一个有）。显然它仍然是一个有l个叶个叶结点的判定树结点的判定树DT，但外部路长，但外部路长epl发生了变化。具体地说有发生了变化。具体地说有三条路长发生了变化：三条路长发生了变化：在在DT上，从根到上，从根到X，Z1，Z2的三条路长为的三条路长为k + 2d。在在DT上，从根
57、到上，从根到Z1，Z2，Y的三条路长为的三条路长为2(k+1)+d-1=2k+d+1。因。因k d 1，所以，所以2k+d+1 k+(d-1)+d+1 = k+2d，得证。，得证。瑞船妹狸拘乙追聂输由虹晰阻但郝授撇彭廷隋痢孟袍殖宰函漱荫朝碘辜宁chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术61引理引理2.10 有有l个叶结点的判定树个叶结点的判定树DT的最小的最小epl可表示为：可表示为： 1l = 2k，有上面引理可以断定，最佳，有上面引理可以断定，最佳DT为完全满二叉树，即为完全满二叉树，即叶结点全在底层，显然叶结点全在底层，显然 ep
58、l = llogl，即为上式。，即为上式。2若若l 2k，设，设DT深度为深度为d，全部叶结点在，全部叶结点在d层和层和d 1层，如层，如Fig.2.16所示。这时，因所示。这时，因 ，因此有下面的定理：因此有下面的定理： 压蛛蹄缔卑追汉缆养羔逞罩洁拓誉铆孟屎拾么鳞迪百褥完揖稠钥计陇衷韦chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术62定理定理2.11 任何任何n元比较排序算法在平均情形下的比较次数至少元比较排序算法在平均情形下的比较次数至少为为log(n!)，即，即A(n)log(n!)nlogn 1.443n证明：证明：因任一因任一n元
59、比较排序算法的判定树的叶结点数元比较排序算法的判定树的叶结点数ln!，且，且所以所以 蓑丸犬肃窿固克棋缠药蛋贬橇趾趟辊雪挟茵坟巢萤扑振彦证肃匝效泛度筑chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术632.6 排序算法的有关研究排序算法的有关研究 比较排序算法的改进与分析比较排序算法的改进与分析 基数排序（基数排序（Radix Sorting） 例如当元素关键字有三位十进制整数组成时，算法如例如当元素关键字有三位十进制整数组成时，算法如Fig.2.17所示。所示。 外部排序算法外部排序算法 粗排序（粗排序（Roughly Sorting） 并
60、行排序（并行排序（Parallel Sorting）第二章完第二章完牙颓若艰裕寸蚤梅程雄猜说侩撑朋艰废橇疙酣酮尔予赡烛狠壶臀恃邦婿福chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术64琶季柄惰陷玩胚佩恼沁穗爽弟藤弧鹿视志霸课趋完嗅恩禾鹊仗孺瞬非拐麻chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术65算法算法 2.1 选择排序算法选择排序算法 SelectSort template void SelectSort ( Key L , int n ) int i, j, k ; for ( i
61、= 1 ; i n ; i + + ) for ( j = i + 1 , k = i ; j Lj ) k = j ; Swap ( Li , Lk ) ; return ;返回返回忠苦宣昧囤喊陆戴晰察瘦彝米僳刑菲拌垂盈玛扯剔勒分肚甜猛沤述返厚赔chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术66算法算法 2.2 插入排序算法插入排序算法 InsertSort template void InsertSort ( Key L , int n ) int i , j ; Key temp ; for ( i = 2 ; i 0 ; j - -
62、 ) if ( Lj temp ) Lj+1 = Lj ; else Lj+1 = temp ; break ; return ;返回返回榴典佛辟没躺盏兵凯燎屠栽疙赛址姆刷刚劳靠粳敬潍可腋循垃蜘肇妹功煞chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术67算法算法 2.3 起泡排序算法起泡排序算法 BubbleSort template void BubbleSort ( Key L , int n ) int i , j ; for ( i = 1 ; i i ; j - - ) if ( Lj Lj-1 ) Swap( Lj , Lj-1
63、) ; return ;返回返回挝亡跋镊同壁奏汐敛村琅兄铂阮注尘毛粱客聊亡考忱吹信榨瞩崖石洋意斟chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术68算法算法 2.4 起泡排序的改进算法起泡排序的改进算法 BSort template void BSort ( Key L , int n ) int p = 1 ; int i , j ; for ( i = 1 ; ( i i ; j - - ) p = 0; if ( Lj Lj-1 ) p = 1 ; Swap( Lj , Lj-1 ) ; return ;返回返回塘迫樊肮哥欲镐桔碘拎冗梅
64、为算先侯迎褂返讽隐烈查圾菲双糜捆依施戮玛chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术69算法算法 2.5 希尔排序算法希尔排序算法 ShellSort template void ShellSort ( Key L , int n , int t , int h ) for ( int h = ht , s = t ; s = 1 ; s - - , h = hs ) for ( int k = 1 ; k = h ; k + + ) for ( int i = h + k ; i temp )&( j 0) ) Lj+h = Lj ;
65、j - = h ; Lj+h = temp ; return ;返回返回变打貉帖捂孜坝娩捌柏偿矩哗榷稍膜洲好父旨庶坏跃粳尸彝柿升疽潜酉酱chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术70算法算法 2.6 快速排序算法快速排序算法 QuickSort template void QuickSort ( Key L , int first , int last ) if ( first last ) int split = Partition ( L , first, last ) ; QuickSort ( L , first , split
66、 1 ) ; QuickSort ( L , split + 1 , last ) ; return ;返回返回果怕韩蔫铃斋委它托菩耍沮盎搬书勘扫佐牺颜全冰烙勾掩僚疹糯萨浸错赤chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术71算法算法 2.7 快速排序的划分算法快速排序的划分算法 Partition template int Partition ( Key L , int first , int last ) int left = first ; int right = last ; Key pivot = Lfirst ; while (
67、 left = pivot ) right - - ; Lleft+ = Lright ; while ( Lleft pivot ) left + + ; Lright- = Lleft ; Lleft = pivot ; return left ;返回返回借锣惰告省诱叭诽膘靴健鬼砰斤署码奥冗舱报楞网拯覆汪占证娇倪雌撩踌chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术72算法算法 2.8 快速排序的改进算法快速排序的改进算法 QStackSort template void QStackSort ( Key L , int n ) int
68、f , l , i ; stack.push( 1 , n ) ; while ( ! stack.empty ) stack.pop ( f , l ) ; while ( f l ) i = Partition ( L , f , l ) ; Stack.push ( i + 1 , l ) ; l = i 1 ; return ;返回返回农呸幸肯舞邵航易飘抽园悬盎登淋圣萨筐猎敬锰拇冷钡显鸦壕耘褐捎奎箔chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术73算法算法 2.9 有序序列的合并算法有序序列的合并算法 Merge template
69、void Merge ( Key S , int l, int m, int r ) Key T ; int i = l ; int j = m + 1 ; int k = l ; while ( ( i = m ) & ( j = r ) ) if ( Si m ) for ( int p = j ; p = r ; p+ ) Tk+ = Sp ; else for ( int p = i ; p = m ; p+ ) Tk+ = Sp ; for ( p = l ; p = r ; p+) Sp = Tp ; return ;返回返回娄厂秒柳嫩眼裹俘需钠桶铰捅损篇驹呸炳舜疗昼闰剃阳掂烩惜本
70、啼骄促酒chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术74算法算法 2.10 合并排序算法合并排序算法 MergeSort template void MergeSort ( Key L , int first, int last ) if ( first last ) int mid = ( first + last ) /2 ; MergeSort( L , first , mid ) ; MergeSort( L , mid + 1 , last) ; Merge( L , first , mid , last ) ; return
71、;返回返回夯匙猿毁棘窿莆声诫腆堰吞儒稽噎宦看热坦助苦苦丧蔚睬准酉秦袍植跃筒chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术75算法算法 2.11 合并排序改进算法合并排序改进算法II MergeSort2 template void MergeSort2 ( Type L , int n ) while ( n 1 ) int i = 1 ; int j , k ; do for ( j = i; ( j n )&( Lj Lj+1 ); j+ ) ; if ( j = n ) return ; for ( k = j ; ( k n )&(
72、 Lk j ) Merge( L, i, j, k ) ; i = k + 1 ; while ( i = n ) return ;返回返回穴攘佣恭宴卯花阎支运迭卖伞莹婚抱粘言燎金饿卯浊继掀革阑瘪慑腆蒋夕chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术76算法算法 2.12 堆排序算法堆排序算法 HeapSort template void HeapSort( Element L , int n ) BuildHeap（ L , n ） ; for( int i = n ; i = 2 ; i - - ) Element temp = Li
73、; Li = L1 ; FixHeap( L , i - 1 , 1 , temp) ; return ; void FixHeap( Element L , int Hsize , int root , Element k ) if( ( 2 * root ) Hsize ) Lroot = k ; else if( ( 2 * root ) = Hsize ) int larger = 2 * root ; else if( L2*root L2*root+1 ) larger = 2 * root ; / 续下页续下页返回返回簇卓眨担象菏哨腔锅若心谓炳邱灶醒琅错蹄婚漓呐彼娃桌继颈藉锈鉴良
74、代chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术77算法算法 2.12 堆排序算法堆排序算法 HeapSort else/ 续上页续上页 larger = 2 * root + 1 ; if( k Llarger ) Lroot = k ; else Lroot = Llarger ; FixHeap( L , Hsize , larger , k) ; return ; void BuildHeap( Element L , int n ) for( int i = n/2 ; i = 1 ; i - - ) FixHeap( L , n
75、 , i , Li ); return ;返回返回茬备蔫埔神谩夷鹤瑚以拿抖材祝柯极苏浇老刀详邢丝疑伶艘乐菱琼翻斡祷chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术78算法算法 2.13 改进的堆恢复过程改进的堆恢复过程 AfixHeap template void AfixHeap( Key L , int Hsize , int vac , Key k ) while ( ( 2 * vac ) Hsize ) if( Lvac*2 Lvac/2 ) Lvac = Lvac/2 ; vac = vac/2 ; Lvac = k ; retu
76、rn ;返回返回倘俯辜嫡挺环镁映躺减拼蛇洱遭颂蘑等林傅刮恨绰阻揪蜒拂阳男显崭渴夜chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术79判定树（判定树（Decision Tree）模型）模型 # include void main( void ) int a , b , c ; cin a b c ; if( a b ) if( b c ) cout a b c ; else if( a c ) cout a c b ; else cout c b a ; else if( a c ) cout b a c ; else if( b c ) cout b c a ; else cout c b a ; return ;返回返回坪川泳滋割甚臣事融冶回陡曾线稽搭橡袖嘶裂裴蹋官牢幼砷漆作瘩儿木付chapter2 Sortin算法和算法的分析技术chapter2 Sortin算法和算法的分析技术80
