数据结构内部排序.pptx

《数据结构内部排序.pptx》由会员分享，可在线阅读，更多相关《数据结构内部排序.pptx（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1目 录10.1 概述10.2 插入排序10.3 快速排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法的比较讨论第1页/共87页2 排序（排序（sorting）1.基本概念 将一个数据元素（或记录）的任意序列，重新排列成将一个数据元素（或记录）的任意序列，重新排列成一个按关键字一个按关键字有序有序的序列。的序列。假设含假设含n个记录的序列为个记录的序列为 R1，R2，Rn (）其相应的关键字序列为其相应的关键字序列为 K1，K2，Kn 10.1 概述第2页/共87页3需确定需确定1，2，n的一种排列的一种排列p1，p2，pn，使其相应，使其相应的关键字满足如

2、下的非递减（或非递增）关系的关键字满足如下的非递减（或非递增）关系 Kp1 Kp2 Kpn即使序列即使序列(）成为一个按关键字有序的序列）成为一个按关键字有序的序列 Rp1，Rp2，Rpn这种操作过程称为排序。这种操作过程称为排序。排序排序(接上页接上页)基本概念第3页/共87页4基本概念 排序方法是稳定的排序方法是稳定的 设设 Ki=Kj（l i n，1 j n，ij），且在排序），且在排序前前的序列中的序列中 Ri领先于领先于 Rj（即（即 ij），在排序），在排序后后的序列中的序列中 Ri仍仍领先于领先于 Rj。排序方法是不稳定的排序方法是不稳定的 设设 Ki=Kj（l i n，1 j

3、n，ij），且在排序前），且在排序前的序列中的序列中 Ri领先于领先于 Rj（即（即 ij），在排序后的序列中），在排序后的序列中 Rj领先于领先于 Ri。第4页/共87页52.排序方法分类 按照文件所处的位置不同：按照文件所处的位置不同：内部排序内部排序 待排序记录存放在计算机待排序记录存放在计算机内存内存中进行的排序过程。中进行的排序过程。外部排序外部排序 排序过程中有内、外存间信息的传递及交换的排序过程。排序过程中有内、外存间信息的传递及交换的排序过程。第5页/共87页6排序方法分类 按排序时使用的原理按排序时使用的原理 插入排序、交换排序、选择排序、归并排序、基数插入排序、交换排序、选

4、择排序、归并排序、基数排序。排序。按照所需的工作量按照所需的工作量简单的排序方法，其时间复杂度为简单的排序方法，其时间复杂度为O（n2）；）；先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O（nlogn）；）；基数排序，其时间复杂度为基数排序，其时间复杂度为O（d n）。）。第6页/共87页73.基本操作 比较比较两个关键字的大小；两个关键字的大小；将记录从一个位置将记录从一个位置移动移动至另一个位置。至另一个位置。第7页/共87页84.存储结构（1）以一维数组作为存储结构）以一维数组作为存储结构（2）以静态链表作为存储结构）以静态链表作为存储结构（链表排序）（链表排序）（3）采

5、用辅助表排序）采用辅助表排序（地址排序）（地址排序）待排序记录存储在数组中，同时另待排序记录存储在数组中，同时另 设一个指示各个记设一个指示各个记录存储位置的录存储位置的地址向量。地址向量。在排序过程中不移动记录本身，而在排序过程中不移动记录本身，而移动地址向量中这些记录的移动地址向量中这些记录的 “地址地址”，排序结束后再按照地，排序结束后再按照地址向量中的值调整记录的存储位置。址向量中的值调整记录的存储位置。第8页/共87页9 5.排序方法分析 排序的时间开销排序的时间开销排序的时间开销排序的时间开销:排序的时间开销是衡量算法好坏排序的时间开销是衡量算法好坏排序的时间开销是衡量算法好坏排序

6、的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的最重要的标志。排序的时间开销可用算法执行中的最重要的标志。排序的时间开销可用算法执行中的最重要的标志。排序的时间开销可用算法执行中的的的的数据比较次数数据比较次数数据比较次数数据比较次数与与与与数据移动次数数据移动次数数据移动次数数据移动次数来衡量。来衡量。来衡量。来衡量。一般都一般都一般都一般都按平均情况按平均情况按平均情况按平均情况进行估算。对于那些受对象关键进行估算。对于那些受对象关键进行估算。对于那些受对象关键进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的，需要字序列初始排列及对象个数影响较大的，需要

7、字序列初始排列及对象个数影响较大的，需要字序列初始排列及对象个数影响较大的，需要按最按最按最按最好情况好情况好情况好情况和和和和最坏情况最坏情况最坏情况最坏情况进行估算。进行估算。进行估算。进行估算。衡量排序方法的标准衡量排序方法的标准衡量排序方法的标准衡量排序方法的标准 排序时所需要的平均比较次数排序时所需要的平均比较次数 排序时所需要的平均移动排序时所需要的平均移动 排序时所需要的平均辅助存储空间排序时所需要的平均辅助存储空间第9页/共87页101.直接插入排序(Straight Insertion Sort)概念概念 将一个记录插入到已排好序的有序表中，从而得到一将一个记录插入到已排好序

8、的有序表中，从而得到一个新的、记录数增个新的、记录数增 1 的有序表。的有序表。例：已排序的一组记录排列如下：例：已排序的一组记录排列如下：12，33，45，57，76现将关键字现将关键字 40 记录插入上述序列中记录插入上述序列中12，33，40，45，57，7610.2 插入排序第10页/共87页11 算法的基本思路算法的基本思路直接插入排序 设有设有n个待排记录存放在个待排记录存放在r1.n中，将第中，将第i(2i n)个记录个记录插入到已排好序的有序表插入到已排好序的有序表r1.i-1中的过程为：从中的过程为：从ri-1 起往起往前搜索，若前搜索，若ri rj(1j i-1)，则将，则

9、将rj 向后移动，直至找向后移动，直至找到第到第i个记录的位置。个记录的位置。第11页/共87页12 算法算法10.1直接插入排序void InsertSort（SqList&L）for(i=2;i=L.Length;+i)if LT(L.ri.key,L.ri-1.key L.r0=L.ri；L.ri=L.ri-1；for(j=i-2;LT(L.r0.key,L.rj.key);-j）L.rj+l=L.rj;L.rj+l=L.r0;第12页/共87页13 例子例子直接插入排序初始关键字：初始关键字：(42)41 33 67 74 23 37 33 i=2：(41)(41 42)33 67 7

10、4 23 37 33 i=3：(33)(33 41 42)67 74 23 37 33i=4：(33)(33 41 42 67)74 23 37 33i=5：(33)(33 41 42 67 74)23 37 33i=6：(23)(23 33 41 42 67 74)37 33 i=7：(37)(23 33 37 41 42 67 74)33 i=8：(33)(23 33 33 37 41 42 67 74)第13页/共87页14时间复杂性分析时间复杂性分析直接插入排序若设待排序的对象个数为若设待排序的对象个数为L.lengthL.length=n n，则该，则该算法的主程序执行算法的主程序执

11、行n n-1-1趟。趟。关键字比较次数和对象移动次数与对象关键字关键字比较次数和对象移动次数与对象关键字的初始排列有关。的初始排列有关。最好情况下，排序前对象已经按关键字大小从最好情况下，排序前对象已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键字比较的最后一个对象的关键字比较 1 1 次，总的关键次，总的关键字比较次数为字比较次数为 n n-1-1，对象移动次数为，对象移动次数为 0 0。最坏情况下，排序前对象已经按关键字大小从最坏情况下，排序前对象已经按关键字大小从大到小有序（逆序），需比较和移动次数为多大到小有序（逆序

12、），需比较和移动次数为多少？少？第14页/共87页15 直接插入排序时间复杂性分析时间复杂性分析若待排序对象序列中出现各种可能排列的概若待排序对象序列中出现各种可能排列的概若待排序对象序列中出现各种可能排列的概若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的率相同，则可取上述最好情况和最坏情况的率相同，则可取上述最好情况和最坏情况的率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数平均情况。在平均情况下的关键字比较次数平均情况。在平均情况下的关键字比较次数平均情况。在平均情况下的关键字比较次数和对象移动次数约为和对象移动次数约为和对象移动次

13、数约为和对象移动次数约为 n n2 2/4/4。因此，直接插入。因此，直接插入。因此，直接插入。因此，直接插入排序的时间复杂度为排序的时间复杂度为排序的时间复杂度为排序的时间复杂度为 o(o(n n2 2)。直接插入排序是一种直接插入排序是一种直接插入排序是一种直接插入排序是一种稳定稳定稳定稳定的排序方法。的排序方法。的排序方法。的排序方法。第15页/共87页162.其它插入排序 折半插入排序折半插入排序（Binary Insertion Sort）折半插入排序基本思想是：设在顺序表中有一折半插入排序基本思想是：设在顺序表中有一折半插入排序基本思想是：设在顺序表中有一折半插入排序基本思想是：设

14、在顺序表中有一 个对象序列个对象序列个对象序列个对象序列 V0,V1,V0,V1,vn-1,vn-1。其中，。其中，。其中，。其中，v0,V1,vi-1 v0,V1,vi-1 是已经排好序的对象。在插入是已经排好序的对象。在插入是已经排好序的对象。在插入是已经排好序的对象。在插入 vi vi 时，利用折半搜索法寻找时，利用折半搜索法寻找时，利用折半搜索法寻找时，利用折半搜索法寻找 vi vi 的插入位置。的插入位置。的插入位置。的插入位置。2-路插入排序路插入排序 表插入排序表插入排序第16页/共87页17 折半插入排序的算法折半插入排序的算法10.210.2void BInsertSort(

15、SqList&L)int low,high,mid;for(int i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high+1;-j)L.r j+1=L.r j;L.rhigh+1=L.r0;说明：low 或者 high+1为插入点 稳定排序第17页/共87页18 算法分析算法分析算法分析算法分析折半查找比顺序查找快，所以折半查找比顺序查找快，所以折半查找比顺序查找快，所以折半查找比顺序查找快，所以折半折半插入排序就平均性能来说比直接插入排序就平均性能来说比直接插入排序就平均性能来说比直接插入排序就平均性能来说比直接插入排序要快。插入

16、排序要快。插入排序要快。插入排序要快。它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。依赖于对象个数。依赖于对象个数。依赖于对象个数。在插入第在插入第在插入第在插入第 i i 个对象时，需要经过个对象时，需要经过个对象时，需要经过个对象时，需要经过 log2ilog2i +1 +1 次关次关次关次关键字比较，才能确定它应插入的位置。键字比较，才能确定它应插入的位置。键字比较，才能确定它应插入的位置

17、。键字比较，才能确定它应插入的位置。因此，将因此，将因此，将因此，将 n n 个对象（为推导个对象（为推导个对象（为推导个对象（为推导方便，设为方便，设为方便，设为方便，设为 n=2k)n=2k)用用用用折半折半插入排序所进行的关键字比较次数为：插入排序所进行的关键字比较次数为：插入排序所进行的关键字比较次数为：插入排序所进行的关键字比较次数为：第18页/共87页19第19页/共87页20 当当当当 n n 较较较较大大大大时时时时，总总总总关关关关键键键键字字字字比比比比较较较较次次次次数数数数比比比比直直直直接接接接插插插插入入入入排排排排序序序序的的的的最坏情况要好得多，但比其最好情况要

18、差。最坏情况要好得多，但比其最好情况要差。最坏情况要好得多，但比其最好情况要差。最坏情况要好得多，但比其最好情况要差。在在在在对对对对象象象象的的的的初初初初始始始始排排排排列列列列已已已已经经经经按按按按关关关关键键键键字字字字排排排排好好好好序序序序或或或或接接接接近近近近有有有有序序序序时时时时，直直直直接接接接插插插插入入入入排排排排序序序序比比比比折折半半插插插插入入入入排排排排序序序序执执执执行行行行的的的的关关关关键键键键字字字字比比比比较较较较次次次次数数数数要要要要少少少少。折折半半插插插插入入入入排排排排序序序序的的的的对对对对象象象象移移移移动动动动次次次次数数数数与与与

19、与直直直直接接接接插入排序相同，依赖于对象的初始排列。插入排序相同，依赖于对象的初始排列。插入排序相同，依赖于对象的初始排列。插入排序相同，依赖于对象的初始排列。折半折半插入排序是一个插入排序是一个插入排序是一个插入排序是一个稳定稳定稳定稳定的排序方法。的排序方法。的排序方法。的排序方法。第20页/共87页213.希尔排序(Shells Sort)基本思想基本思想 先将整个待排记录序列分割成为若干先将整个待排记录序列分割成为若干子序列子序列分别进行分别进行直接插入排序直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时，再对时，再对全体记录全体记录进行一次进行一次直接插入

20、排序直接插入排序。概念概念 希尔排序又称希尔排序又称“缩小增量排序缩小增量排序”(Diminishing Increment Sort)属于插入排序类的方法，其时间效率上优于前述几种方法。属于插入排序类的方法，其时间效率上优于前述几种方法。第21页/共87页22例，初始关键字序列为：例，初始关键字序列为：43 41 33 67 74 23 37 33 47 35d=5 43 2341 3733 3367 4774 35一趟排序的结果：一趟排序的结果：23 37 33 47 35 43 41 33 67 74希尔排序 例子例子第22页/共87页23 23 37 33 47 35 43 41 33

21、 67 74d=3 23 47 41 7437 35 3333 43 67二趟排序的结果：二趟排序的结果：23 33 33 41 35 43 47 37 67 74三趟排序三趟排序(直接插入排序直接插入排序)的结果：的结果：23 33 33 35 37 41 43 47 67 74希尔排序第23页/共87页24 10.3 交换排序 交换排序交换排序 (Exchange Sort)(Exchange Sort)交换排序的基本思想是两两比较待排序交换排序的基本思想是两两比较待排序对象的关键字，如果发生逆序对象的关键字，如果发生逆序(即排列顺即排列顺序与排序后的次序正好相反序与排序后的次序正好相反)

22、，则交换之，则交换之，直到所有对象都排好序为止。直到所有对象都排好序为止。第24页/共87页25 基本思想基本思想 将第将第1个记录的关键字和第个记录的关键字和第2个记录的关键字进行比较，若为个记录的关键字进行比较，若为逆序逆序（即（即r1.keyr2.key），则将两个记录），则将两个记录交换交换之，然后比较第之，然后比较第2个记录和第个记录和第3个记录个记录的关键字。依次类推，直至第的关键字。依次类推，直至第n-1个记录和第个记录和第n个记录的关键字进行过比较为止。个记录的关键字进行过比较为止。第一趟冒泡排序后，关键字最大的记录被放到最后一个记录的位置上。第一趟冒泡排序后，关键字最大的记录

23、被放到最后一个记录的位置上。对前对前n-1个记录进行同样操作，其结果是使关键字次大个记录进行同样操作，其结果是使关键字次大的记录被安置到第的记录被安置到第 n-1个记录的位置上。个记录的位置上。1.冒泡排序(Bubble Sort)第25页/共87页26 一般地，第一般地，第 i 趟冒泡排序是从趟冒泡排序是从 r1到到 rn-i+1依次比较相邻两个记录的关键依次比较相邻两个记录的关键字，并在字，并在“逆序逆序”时时交换交换相邻记录，其结果是这相邻记录，其结果是这n-i+1个记录中关键字最大的记个记录中关键字最大的记录被交换到第录被交换到第n-i+1 的位置上。整个排序过程需进行的位置上。整个排

24、序过程需进行k（1 k 1&change;-I)change=false;for(j=0;jaj+1)aj aj+1;change=TURE 算法复杂性分析：最好情况（正序）：一趟排序，n-1次比较，移动0个记录 最坏情况（逆序）：n-1趟排序，n-1+n-2+1=n(n-1/)/2 次比较,移动n(n-1/)/2个记录 时间复杂度：O(n2)第28页/共87页292.快速排序(Quick Sort)基本思想基本思想 根根据据选选定定的的支支点点L，通通过过一一趟趟排排序序将将待待排排记记录录分分割割成成独独立立的的两两部部分分，其其中中一一部部分分记记录录的的关关键键字字均均小小于于L，而而

25、另另一一部部分分记记录录的的关关键键字字均均大大于于等等于于L。分分别对这两部分记录继续进行排序，以达到整个序列有序别对这两部分记录继续进行排序，以达到整个序列有序。支点的选择方法支点的选择方法 取第一个记录；最后一个记录；第一个、最后一个和取第一个记录；最后一个记录；第一个、最后一个和中间记录三者中，关键字居中的那个记录。中间记录三者中，关键字居中的那个记录。第29页/共87页30 具体做法具体做法 设待排序的序列为设待排序的序列为rs，rs+1，rt。附设。附设两个指针两个指针i和和j，它们的初值分别为，它们的初值分别为s和和t，设支点记录，设支点记录pivot=rs，x=pivotkey

26、。则首先从。则首先从j所指位置起向前搜索找到第所指位置起向前搜索找到第一个关键字小于一个关键字小于x的记录和的记录和pivot互相交换，然后从互相交换，然后从i所指位置所指位置起向后搜索，找到第一个关键字大于起向后搜索，找到第一个关键字大于x的记录和的记录和pivot互相交互相交换，重复这两步直至换，重复这两步直至i=j为止。为止。快速排序第30页/共87页31 举例举例 例，初始关键字序列为：例，初始关键字序列为：43 41 33 67 74 23 37 33 47 35 x=43 初始初始 43 41 33 67 74 23 37 33 47 35 i j 1次次 35 41 33 67

27、74 23 37 33 47 43 i i j 快速排序第31页/共87页322次次 35 41 33 43 74 23 37 33 47 67 i j 3次次 35 41 33 33 74 23 37 43 47 67 i j j 4次次 35 41 33 33 43 23 37 74 47 67 i i j快速排序第32页/共87页335次次 35 41 33 33 37 23 43 74 47 67 i j j快速排序5次次 35 41 33 33 37 23 43 74 47 67 i j完成一趟完成一趟 35 41 33 33 37 23 43 74 47 67第33页/共87页34

28、快速排序的算法void QSort(SqList&L,int low,int high)if(low high)int pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);PrintST(L);QSort(L,pivotloc+1,high);PrintST(L);void QuickSort(SqList&L)QSort(L,1,L.length);第34页/共87页35int Partition(SqList&L,int low,int high)L.r0=L.rlow;int pivotkey=L.rlow.key;while(l

29、ow high)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;第35页/共87页36 算法分析从快速排序算法的递归树可知，快速排序的趟数取决于递归树从快速排序算法的递归树可知，快速排序的趟数取决于递归树从快速排序算法的递归树可知，快速排序的趟数取决于递归树从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。的深度。的深度。的深度。如果每次划分对一个对象定位后，该对象的左侧子序列与右侧如果每次划分对一

30、个对象定位后，该对象的左侧子序列与右侧如果每次划分对一个对象定位后，该对象的左侧子序列与右侧如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进子序列的长度相同，则下一步将是对两个长度减半的子序列进子序列的长度相同，则下一步将是对两个长度减半的子序列进子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。行排序，这是最理想的情况。行排序，这是最理想的情况。行排序，这是最理想的情况。在在在在n n个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为

31、个元素的序列中，对一个对象定位所需时间为 O(O(n n)。若设。若设。若设。若设 t(t(n n)是对是对是对是对 n n 个元素的序列进行排序所需的时间，而且每次对一个元素的序列进行排序所需的时间，而且每次对一个元素的序列进行排序所需的时间，而且每次对一个元素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，个对象正确定位后，正好把序列划分为长度相等的两个子序列，个对象正确定位后，正好把序列划分为长度相等的两个子序列，个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：此时，总的计算时间为：此时，总的计算时间为：此时，总

32、的计算时间为：第36页/共87页37T(T(n n)cncn+2 t(+2 t(n n/2)/2)/c c是一个常数是一个常数是一个常数是一个常数 CnCn+2(+2(cncn/2+2t(/2+2t(n n/4)=2/4)=2cn cn+4t(+4t(n n/4)/4)2 2cn cn+4(+4(cncn/4+2t(/4+2t(n n/8)=3/8)=3cncn+8t(+8t(n n/8)/8)CnCn log log2 2n n+n nt(1)=o(t(1)=o(n n log log2 2n n)可可可可以以以以证证证证明明明明，函函函函数数数数quicksortquicksort的的的的

33、平平平平均均均均计计计计算算算算时时时时间间间间也也也也是是是是o(o(n nloglog2 2n n)。实实实实验验验验结结结结果果果果表表表表明明明明：就就就就平平平平均均均均计计计计算算算算时时时时间间间间而而而而言言言言，快快快快速速速速排排排排序序序序是是是是我我我我们们们们所所所所讨讨讨讨论论论论的的的的所所所所有内排序方法中最好的一个有内排序方法中最好的一个有内排序方法中最好的一个有内排序方法中最好的一个。第37页/共87页38 快快快快速速速速排排排排序序序序是是是是递递递递归归归归的的的的，需需需需要要要要有有有有一一一一个个个个栈栈栈栈存存存存放放放放每每每每层层层层递递递

34、递归归归归调用时的指针和参数。调用时的指针和参数。调用时的指针和参数。调用时的指针和参数。最最最最大大大大递递递递归归归归调调调调用用用用层层层层次次次次数数数数与与与与递递递递归归归归树树树树的的的的深深深深度度度度一一一一致致致致，理理理理想想想想情情情情 况况况况 为为为为 loglog2 2(n n+1)+1)。因因因因 此此此此，要要要要 求求求求 存存存存 储储储储 开开开开 销销销销 为为为为 o(logo(log2 2n n)。在在在在最最最最坏坏坏坏的的的的情情情情况况况况，即即即即待待待待排排排排序序序序对对对对象象象象序序序序列列列列已已已已经经经经按按按按其其其其关关关

35、关键键键键字字字字从从从从小小小小到到到到大大大大排排排排好好好好序序序序的的的的情情情情况况况况下下下下，其其其其递递递递归归归归树树树树成成成成为为为为单单单单支支支支树树树树，每每每每次次次次划划划划分分分分只只只只得得得得到到到到一一一一个个个个比比比比上上上上一一一一次次次次少少少少一一一一个个个个对对对对象象象象的的的的子子子子序序序序列列列列。这这这这样样样样，必必必必须须须须经经经经过过过过 n n-1-1 趟趟趟趟才才才才能能能能把把把把所所所所有有有有对对对对象象象象定定定定位位位位，而而而而且且且且第第第第 i i 趟趟趟趟需需需需要要要要经经经经过过过过 n n-i i

36、 次次次次关关关关键键键键字字字字比比比比较较较较才才才才能能能能找找找找到到到到第第第第 i i 个个个个对对对对象象象象的的的的安安安安放放放放位位位位置置置置，总总总总的的的的关关关关键键键键字字字字比比比比较较较较次次次次数将达到数将达到数将达到数将达到第38页/共87页39其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储储(即栈即栈)将达到将达到o(o(n n)。若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以

37、加速排序速度，但是由于对象的初始排列次序个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。是随机的，这个要求很难办到。有一种改进办法：取每个待排序对象序列的第一个对象、最后一个对象有一种改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的和位置接近正中的3 3个对象，取其关键字居中者作为基准对象。个对象，取其关键字居中者作为基准对象。快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。对于对于 n n 较大的平均情况而言，快速排序是较大的平均情况而言，快速排序是“快速快速”的，但是当的，但是当 n n 很小时，很小时，这种

38、排序方法往往比其它简单排序方法还要慢。这种排序方法往往比其它简单排序方法还要慢。第39页/共87页40 基本思想基本思想 每一趟在每一趟在 n-i+1（i=1，2，n-1）个记录中选取关）个记录中选取关键字键字最小最小的记录作为有序序列中第的记录作为有序序列中第 i 个记录。个记录。分类分类 简单选择排序简单选择排序 树形选择排序树形选择排序 堆排序堆排序10.4 选择排序第40页/共87页411.简单选择排序(Simple Selection Sort)基本思想基本思想 通过通过 n-i次关键字间的比较，从次关键字间的比较，从 n-i+1个记录中选出关个记录中选出关键字最小的记录，并和第键字

39、最小的记录，并和第i（1 i n）个记录交换之（称为）个记录交换之（称为一趟简单选择排序）。具体实现时令一趟简单选择排序）。具体实现时令 i 从从1至至n-1，进行，进行n-1次选择操作。次选择操作。第41页/共87页42 算法算法void SelectSort（SqList&L）for(i=1;iL.Length;+i)k=i;for(j=i+1;j=L.Length;+j)if (L.rj.keyL.rk.key)k=j；if(i!=k)L.r0=L.ri;L.ri=L.rk;L.rk=L.r0;简单选择排序第42页/共87页43简单选择排序 举例举例4938659776132749初始关

40、键字1338659776492749第一趟排序后1327659776493849第二趟排序后1327389776496549第三趟排序后1327384976976549第四趟排序后1327384949976576第五趟排序后1327384949659776第六趟排序后1327384949657697第七趟排序后第43页/共87页44 算法分析 直接选择排序的关键字比较次数直接选择排序的关键字比较次数直接选择排序的关键字比较次数直接选择排序的关键字比较次数KCNKCN与对象的初始排列无关。第与对象的初始排列无关。第与对象的初始排列无关。第与对象的初始排列无关。第 i i 趟趟趟趟选择具有最小关键

41、字对象所需的比较次数总是选择具有最小关键字对象所需的比较次数总是选择具有最小关键字对象所需的比较次数总是选择具有最小关键字对象所需的比较次数总是 n n-i i-1 1 次，此处假定整次，此处假定整次，此处假定整次，此处假定整个待排序对象序列有个待排序对象序列有个待排序对象序列有个待排序对象序列有 n n 个对象。因此，总的关键字比较次数为个对象。因此，总的关键字比较次数为个对象。因此，总的关键字比较次数为个对象。因此，总的关键字比较次数为第44页/共87页45 对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数与对象序列的初始排列有关。

42、当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数对象的移动次数对象的移动次数对象的移动次数RMN RMN=0=0，达到最少。，达到最少。，达到最少。，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为最坏情况是每一趟都要进行交换，总的对象移动次数为最坏情况是每一趟都要进行交换，总的对象移动次数为最坏情况是每一趟都要进行交换，总的对象移动次数为RMNRMN=3(=3(n n-1)1)。直接

43、选择排序是一种直接选择排序是一种直接选择排序是一种直接选择排序是一种不稳定不稳定不稳定不稳定的排序方法。的排序方法。的排序方法。的排序方法。第45页/共87页462.锦标赛排序(Tournament Tree Sort)树形选择排序(Tree Selection Sort)它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得 n n 个对象的关键字，进行个对象的关键字，进行个对象的关键字，进行个对象的关键字，进行两两比较，得到两两比较，得到两两比较，得到两两比较，得到 n n/2

44、/2 个比较的优胜者个比较的优胜者个比较的优胜者个比较的优胜者(关键字小者关键字小者关键字小者关键字小者)，作为第一步比较的结，作为第一步比较的结，作为第一步比较的结，作为第一步比较的结果保留下来。然后对这果保留下来。然后对这果保留下来。然后对这果保留下来。然后对这 n n/2/2 个对象再进行关键字的两两比较，个对象再进行关键字的两两比较，个对象再进行关键字的两两比较，个对象再进行关键字的两两比较，如此重，如此重，如此重，如此重复，直到选出一个关键字最小的对象为止。复，直到选出一个关键字最小的对象为止。复，直到选出一个关键字最小的对象为止。复，直到选出一个关键字最小的对象为止。第46页/共8

45、7页47锦标赛排序构成的树是满的完全二叉树，其深度为锦标赛排序构成的树是满的完全二叉树，其深度为锦标赛排序构成的树是满的完全二叉树，其深度为锦标赛排序构成的树是满的完全二叉树，其深度为 loglog2 2(n n+1)+1)，其中，其中，其中，其中 n n 为待排序元素个数。为待排序元素个数。为待排序元素个数。为待排序元素个数。除第一次选择具有最小关键字的对象需要进行除第一次选择具有最小关键字的对象需要进行除第一次选择具有最小关键字的对象需要进行除第一次选择具有最小关键字的对象需要进行 n n-1-1 次关键字比次关键字比次关键字比次关键字比较外，重构胜者树选择具有次小、再次小关键字对象所需的

46、关较外，重构胜者树选择具有次小、再次小关键字对象所需的关较外，重构胜者树选择具有次小、再次小关键字对象所需的关较外，重构胜者树选择具有次小、再次小关键字对象所需的关键字比较次数均为键字比较次数均为键字比较次数均为键字比较次数均为 O(logO(log2 2n n)。总关键字比较次数为。总关键字比较次数为。总关键字比较次数为。总关键字比较次数为O(O(n nloglog2 2n n)。对象的移动次数不超过关键字的比较次数，所以锦标赛排序总对象的移动次数不超过关键字的比较次数，所以锦标赛排序总对象的移动次数不超过关键字的比较次数，所以锦标赛排序总对象的移动次数不超过关键字的比较次数，所以锦标赛排序

47、总的时间复杂度为的时间复杂度为的时间复杂度为的时间复杂度为O(O(n nloglog2 2n n)。这种排序方法虽然减少了许多排序时间，但是使用了较多的附这种排序方法虽然减少了许多排序时间，但是使用了较多的附这种排序方法虽然减少了许多排序时间，但是使用了较多的附这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。加存储。加存储。加存储。算法分析第47页/共87页48 胜者树的概念每每每每次次次次两两两两两两两两比比比比较较较较的的的的结结结结果果果果是是是是把把把把关关关关键键键键字字字字小小小小者者者者作作作作为为为为优优优优胜胜胜胜者者者者上上上上升升升升到到到到双双双双亲亲亲亲

48、结结结结点，称这种比赛树为胜者树。点，称这种比赛树为胜者树。点，称这种比赛树为胜者树。点，称这种比赛树为胜者树。位位位位于于于于最最最最底底底底层层层层的的的的叶叶叶叶结结结结点点点点叫叫叫叫做做做做胜胜胜胜者者者者树树树树的的的的外外外外结结结结点点点点，非非非非叶叶叶叶结结结结点点点点称称称称为为为为胜胜胜胜者者者者树树树树的的的的内内内内结结结结点点点点。每每每每个个个个结结结结点点点点除除除除了了了了存存存存放放放放对对对对象象象象的的的的关关关关键键键键字字字字 key key 外外外外，还还还还存存存存放放放放了了了了此此此此对对对对象象象象是是是是否否否否要要要要参参参参选选选选

49、的的的的标标标标志志志志 Active Active 和和和和此此此此对对对对象象象象在在在在满满满满二二二二叉叉叉叉树树树树中中中中的的的的序序序序号号号号indexindex。胜者树最顶层是树的根，表示最后选择出来的具有最小关键字胜者树最顶层是树的根，表示最后选择出来的具有最小关键字胜者树最顶层是树的根，表示最后选择出来的具有最小关键字胜者树最顶层是树的根，表示最后选择出来的具有最小关键字的对象。的对象。的对象。的对象。第48页/共87页49如果有如果有如果有如果有 n n 个对象，必须使用至少个对象，必须使用至少个对象，必须使用至少个对象，必须使用至少 2 2n n-1-1 个结点个结点

50、个结点个结点来存放胜者树。最多需要找到满足来存放胜者树。最多需要找到满足来存放胜者树。最多需要找到满足来存放胜者树。最多需要找到满足 2 2k k-1 1 n n 2 2k k 的的的的k k，使用，使用，使用，使用 2*22*2k k-1 1 个结点。每个结点包括个结点。每个结点包括个结点。每个结点包括个结点。每个结点包括关键字、对象序号和比较标志三种信息。关键字、对象序号和比较标志三种信息。关键字、对象序号和比较标志三种信息。关键字、对象序号和比较标志三种信息。锦标赛排序是一个稳定的排序方法。锦标赛排序是一个稳定的排序方法。锦标赛排序是一个稳定的排序方法。锦标赛排序是一个稳定的排序方法。第