数据结构内部排序学习教案.pptx

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

1、会计学1数据结构数据结构(sh j ji u)内部排序内部排序第一页，共87页。2目目 录录10.1 概述概述(i sh)10.2 插入排序插入排序10.3 快速快速(kui s)排序排序10.4 选择选择(xunz)排序排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较讨论各种内部排序方法的比较讨论第1页/共87页第二页，共87页。3 排序排序(pi x)（sorting）1.基本概念基本概念 将一个数据元素将一个数据元素(yun s)（或记录）的任意序列，重新排列成（或记录）的任意序列，重新排列成一个按关键字有序的序列。一个按关键字有序的序列。假设含假

2、设含n个记录的序列个记录的序列(xli)为为 R1，R2，Rn (）其相应的关键字序列其相应的关键字序列(xli)为为 K1，K2，Kn 10.1 10.1 概述概述概述概述第2页/共87页第三页，共87页。4需确定需确定(qudng)1，2，n的一种排列的一种排列p1，p2，pn，使其相应，使其相应的关键字满足如下的非递减（或非递增）关系的关键字满足如下的非递减（或非递增）关系 Kp1 Kp2 Kpn即使序列即使序列(）成为一个按关键字有序的序列）成为一个按关键字有序的序列 Rp1，Rp2，Rpn这种操作过程称为排序。这种操作过程称为排序。排序排序(pi x)(接上页接上页)基本概念基本概念

3、第3页/共87页第四页，共87页。5基本概念基本概念 排序排序(pi x)方法是稳定的方法是稳定的 设设 Ki=Kj（l i n，1 j n，ij），且在排序前），且在排序前的序列的序列(xli)中中 Ri领先于领先于 Rj（即（即 ij），在排序后的序列），在排序后的序列(xli)中中 Ri仍仍领先于领先于 Rj。排序方法排序方法(fngf)是不稳定的是不稳定的 设设 Ki=Kj（l i n，1 j n，ij），且在排序前），且在排序前的序列中的序列中 Ri领先于领先于 Rj（即（即 ij），在排序后的序列中），在排序后的序列中 Rj领先于领先于 Ri。第4页/共87页第五页，共87页。62

4、.排序排序(pi x)方法分方法分类类 按照文件所处的位置不同：按照文件所处的位置不同：内部内部(nib)排序排序 待排序记录存放待排序记录存放(cnfng)在计算机内存中进行的排序过程。在计算机内存中进行的排序过程。外部排序外部排序 排序过程中有内、外存间信息的传递及交换的排序过程。排序过程中有内、外存间信息的传递及交换的排序过程。第5页/共87页第六页，共87页。7排序方法排序方法(fngf)分类分类 按排序按排序(pi x)时使用的原理时使用的原理 插入排序、交换排序、选择排序、归并插入排序、交换排序、选择排序、归并(gubng)排序、基数排序、基数排序。排序。按照所需的工作量按照所需的

5、工作量简单的排序方法，其时间复杂度为简单的排序方法，其时间复杂度为O（n2）；）；先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O（nlogn）；）；基数排序，其时间复杂度为基数排序，其时间复杂度为O（d n）。）。第6页/共87页第七页，共87页。83.基本操作基本操作 比较比较(bjio)两个关键字的大小；两个关键字的大小；将记录从一个位置将记录从一个位置(wi zhi)移动至另一个位置移动至另一个位置(wi zhi)。第7页/共87页第八页，共87页。94.存储存储(cn ch)结构结构（1）以一维数组作为存储）以一维数组作为存储(cn ch)结构结构（2）以静态链表作为存

6、储）以静态链表作为存储(cn ch)结构（链表排序）结构（链表排序）（3）采用辅助表排序）采用辅助表排序（地址排序）（地址排序）待排序记录存储在数组中，同时另待排序记录存储在数组中，同时另 设一个指示各个记设一个指示各个记录存储位置的录存储位置的地址向量。地址向量。在排序过程中不移动记录本身，而在排序过程中不移动记录本身，而移动地址向量中这些记录的移动地址向量中这些记录的 “地址地址”，排序结束后再按照地，排序结束后再按照地址向量中的值调整记录的存储位置。址向量中的值调整记录的存储位置。第8页/共87页第九页，共87页。10 5.5.排序方法排序方法排序方法排序方法(fngf)(fngf)分析

7、分析分析分析n n排序的时间开销排序的时间开销排序的时间开销排序的时间开销:排序的时间开销是衡量算法好坏的最重要的排序的时间开销是衡量算法好坏的最重要的排序的时间开销是衡量算法好坏的最重要的排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据标志。排序的时间开销可用算法执行中的数据比较次数与数据标志。排序的时间开销可用算法执行中的数据比较次数与数据标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。移动次数来衡量。移动次数来衡量。移动次数来衡量。n n一般都按平均情况进行估算。对于一般都按平均情况进行估算。对于一般都按平均情况进行估算。

8、对于一般都按平均情况进行估算。对于(duy)(duy)那些受对象关键字序那些受对象关键字序那些受对象关键字序那些受对象关键字序列初始排列及对象个数影响较大的，需要按最好情况和最坏情列初始排列及对象个数影响较大的，需要按最好情况和最坏情列初始排列及对象个数影响较大的，需要按最好情况和最坏情列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。况进行估算。况进行估算。况进行估算。n n衡量排序方法的标准衡量排序方法的标准衡量排序方法的标准衡量排序方法的标准n n排序时所需要的平均比较次数排序时所需要的平均比较次数排序时所需要的平均比较次数排序时所需要的平均比较次数n n排序时所需要的平

9、均移动排序时所需要的平均移动排序时所需要的平均移动排序时所需要的平均移动n n排序时所需要的平均辅助存储空间排序时所需要的平均辅助存储空间排序时所需要的平均辅助存储空间排序时所需要的平均辅助存储空间第9页/共87页第十页，共87页。111.直接直接(zhji)插入排序插入排序(Straight Insertion Sort)概念概念(ginin)将一个记录插入到已排好序的有序表中，从而将一个记录插入到已排好序的有序表中，从而(cng r)得到一得到一个新的、记录数增个新的、记录数增 1 的有序表。的有序表。例：已排序的一组记录排列如下：例：已排序的一组记录排列如下：12，33，45，57，76

10、现将关键字现将关键字 40 记录插入上述序列中记录插入上述序列中12，33，40，45，57，7610.2 10.2 插入排序插入排序插入排序插入排序第10页/共87页第十一页，共87页。12 算法算法(sun f)的基本思路的基本思路直接直接(zhji)插入排序插入排序 设有设有n个待排记录存放个待排记录存放(cnfng)在在r1.n中，将第中，将第i(2i n)个记录个记录插入到已排好序的有序表插入到已排好序的有序表r1.i-1中的过程为：从中的过程为：从ri-1 起往起往前搜索，若前搜索，若ri rj(1j i-1)，则将，则将rj 向后移动，直至找向后移动，直至找到第到第i个记录的位置

11、。个记录的位置。第11页/共87页第十二页，共87页。13 算法算法(sun f)10.1直接直接(zhji)插入排序插入排序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页第十三页，共87页。14 例子例子(l zi)直接直接(zhji)插入排序插入排序初始初始(ch sh)关键字：关键字：(42)41 33 67 7

12、4 23 37 33 i=2：(41)(41 42)33 67 74 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页第十四页，共87页。15时间时间(shjin)复杂性分析复杂性分析直接直接(zhji)插入排序插入排序n

13、 n若设待排序的对象个数为若设待排序的对象个数为若设待排序的对象个数为若设待排序的对象个数为L.length=nL.length=n，则该算法的主，则该算法的主，则该算法的主，则该算法的主程序执行程序执行程序执行程序执行n-1n-1趟。趟。趟。趟。n n关键字比较次数和对象移动次数与对象关键字的初始关键字比较次数和对象移动次数与对象关键字的初始关键字比较次数和对象移动次数与对象关键字的初始关键字比较次数和对象移动次数与对象关键字的初始排列有关。排列有关。排列有关。排列有关。n n最好情况最好情况最好情况最好情况(qngkung)(qngkung)下，排序前对象已经按关键字下，排序前对象已经按关

14、键字下，排序前对象已经按关键字下，排序前对象已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列大小从小到大有序，每趟只需与前面的有序对象序列大小从小到大有序，每趟只需与前面的有序对象序列大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键字比较的最后一个对象的关键字比较的最后一个对象的关键字比较的最后一个对象的关键字比较 1 1 次，总的关键字比较次，总的关键字比较次，总的关键字比较次，总的关键字比较次数为次数为次数为次数为 n-1 n-1，对象移动次数为，对象移动次数为，对象移动次数为，对象移动次数为 0 0。n n最坏情况最坏情况最坏情况最坏情况(qngkung)(q

15、ngkung)下，排序前对象已经按关键字下，排序前对象已经按关键字下，排序前对象已经按关键字下，排序前对象已经按关键字大小从大到小有序（逆序），需比较和移动次数为多大小从大到小有序（逆序），需比较和移动次数为多大小从大到小有序（逆序），需比较和移动次数为多大小从大到小有序（逆序），需比较和移动次数为多少？少？少？少？第14页/共87页第十五页，共87页。16 直接直接直接直接(zhji)(zhji)插入排序插入排序插入排序插入排序时间时间(shjin)复杂性分析复杂性分析n n若待排序对象序列中出现各种可能排列若待排序对象序列中出现各种可能排列若待排序对象序列中出现各种可能排列若待排序对象序列

16、中出现各种可能排列(pili)(pili)的概率相同，则可取上述最好情况和的概率相同，则可取上述最好情况和的概率相同，则可取上述最好情况和的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字最坏情况的平均情况。在平均情况下的关键字最坏情况的平均情况。在平均情况下的关键字最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为比较次数和对象移动次数约为比较次数和对象移动次数约为比较次数和对象移动次数约为 n2/4 n2/4。因此，直。因此，直。因此，直。因此，直接插入排序的时间复杂度为接插入排序的时间复杂度为接插入排序的时间复杂度为接插入排序的时间复杂度为 o(n2

17、)o(n2)。n n直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。第15页/共87页第十六页，共87页。172.其它其它(qt)插入排序插入排序 折半插入排序（折半插入排序（Binary Insertion Sort）折半插入排序基本思想是：设在顺序表中有一折半插入排序基本思想是：设在顺序表中有一 个个对象序列对象序列 V0,V1,vn-1。其中，。其中，v0,V1,vi-1 是已经排好序的对象。在插入是已经排好序的对象。在插入 vi 时，利时，利用折半搜索法寻找用折半搜索法寻找(xnzho)vi 的插入

18、位置。的插入位置。2-路插入排序路插入排序 表插入排序表插入排序第16页/共87页第十七页，共87页。18n n折半插入排序的算法折半插入排序的算法折半插入排序的算法折半插入排序的算法10.210.2n nvoid BInsertSort(SqList&L)void BInsertSort(SqList&L)n n int low,high,mid;int low,high,mid;n n for(int i=2;i=L.length;+i)for(int i=2;i=L.length;+i)n n L.r0=L.ri;L.r0=L.ri;n n low=1;high=i-1;low=1;hi

19、gh=i-1;n n while(low=high)while(low=high+1;-j)L.rj+1=L.rj;for(int j=i-1;j=high+1;-j)L.rj+1=L.rj;n n L.rhigh+1=L.r0;L.rhigh+1=L.r0;n n n n n n说明：说明：说明：说明：low low 或者或者或者或者 high+1 high+1为插入点为插入点为插入点为插入点 稳定稳定稳定稳定(wndng)(wndng)排序排序排序排序第17页/共87页第十八页，共87页。19n n算法算法算法算法(sun f)(sun f)分析分析分析分析折半查找比顺序查找快，所以折半插

20、入排序就平均性能来说比直接插入排序要快。折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第它所需要的关键字比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。在插入第 i i 个对象

21、时，需要经过个对象时，需要经过个对象时，需要经过个对象时，需要经过 log2ilog2i +1 +1 次关键字比较，才能次关键字比较，才能次关键字比较，才能次关键字比较，才能(cinng)(cinng)确定它应插入的位置。因此，将确定它应插入的位置。因此，将确定它应插入的位置。因此，将确定它应插入的位置。因此，将 n n 个对象（为推导方便，设为个对象（为推导方便，设为个对象（为推导方便，设为个对象（为推导方便，设为 n=2k)n=2k)用折半插入排序所进行的关键字比较次数为：用折半插入排序所进行的关键字比较次数为：用折半插入排序所进行的关键字比较次数为：用折半插入排序所进行的关键字比较次数为

22、：第18页/共87页第十九页，共87页。20第19页/共87页第二十页，共87页。21n n当当当当 n n 较较较较大大大大时时时时，总总总总关关关关键键键键字字字字比比比比较较较较次次次次数数数数比比比比直直直直接接接接插插插插入入入入排排排排序序序序的的的的最最最最坏坏坏坏情情情情况况况况要要要要好得多，但比其最好情况要差。好得多，但比其最好情况要差。好得多，但比其最好情况要差。好得多，但比其最好情况要差。n n在在在在对对对对象象象象的的的的初初初初始始始始(ch(ch sh)sh)排排排排列列列列已已已已经经经经按按按按关关关关键键键键字字字字排排排排好好好好序序序序或或或或接接接接

23、近近近近有有有有序序序序时时时时，直直直直接接接接插插插插入入入入排排排排序序序序比比比比折折折折半半半半插插插插入入入入排排排排序序序序执执执执行行行行的的的的关关关关键键键键字字字字比比比比较较较较次次次次数数数数要要要要少少少少。折折折折半半半半插插插插入入入入排排排排序序序序的的的的对对对对象象象象移移移移动动动动次次次次数数数数与与与与直直直直接接接接插插插插入入入入排排排排序序序序相相相相同同同同，依依依依赖赖赖赖于于于于对对对对象象象象的初始的初始的初始的初始(ch sh)(ch sh)排列。排列。排列。排列。n n折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方

24、法。折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。第20页/共87页第二十一页，共87页。223.希尔排序希尔排序(pi x)(Shells Sort)基本基本(jbn)(jbn)思想思想 先将整个待排记录序列分割成为若干先将整个待排记录序列分割成为若干(rugn)子序列分别进行子序列分别进行直接插入排序，待整个序列中的记录直接插入排序，待整个序列中的记录“基本有序基本有序”时，再对时，再对全体记录进行一次直接插入排序。全体记录进行一次直接插入排序。概念概念 希尔排序又称希尔排序又称“缩小增量排序缩小增量排序”(Diminishing Increment Sort)属于插

25、入排序类的方法，其时间效率上优于前述几种方法。属于插入排序类的方法，其时间效率上优于前述几种方法。第21页/共87页第二十二页，共87页。23例，初始例，初始(ch sh)关键字序列为：关键字序列为：43 41 33 67 74 23 37 33 47 35d=5 43 2341 3733 3367 4774 35一趟排序一趟排序(pi x)的结果：的结果：23 37 33 47 35 43 41 33 67 74希尔排序希尔排序(pi x)例子例子第22页/共87页第二十三页，共87页。24 23 37 33 47 35 43 41 33 67 74d=3 23 47 41 7437 35

26、3333 43 67二趟排序二趟排序(pi x)的结果：的结果：23 33 33 41 35 43 47 37 67 74三趟排序三趟排序(直接直接(zhji)插入排序插入排序)的结果：的结果：23 33 33 35 37 41 43 47 67 74希尔排序希尔排序(pi x)第23页/共87页第二十四页，共87页。25 10.3 10.3 交换交换交换交换(jiohun)(jiohun)排序排序排序排序n n交 换(jiohun)排 序 (Exchange Sort)n n n n 交换(jiohun)排序的基本思想是两两比较待排序对象的关键字，如果发生逆序(即排列顺序与排序后的次序 正

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

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

29、邻记录(jl)，其结果是这，其结果是这n-i+1个记录个记录(jl)中关键字最大的记录中关键字最大的记录(jl)被交换到第被交换到第n-i+1 的位置上。整个排序过程需进行的位置上。整个排序过程需进行k（1 k 1&change;-I)for(I=n-1;change=TURE;I1&change;-I)change=false;change=false;for(j=0;jI;+j)for(j=0;jaj+1)aj aj+1;change=TURE if(ajaj+1)aj aj+1;change=TURE 算法复杂性分析(fnx)：最好情况（正序）：一趟排序，n-1次比较，移动0个记录 最坏

30、情况（逆序）：n-1趟排序，n-1+n-2+1=n(n-1/)/2 次比较,移动n(n-1/)/2个记录 时间复杂度：O(n2)第28页/共87页第二十九页，共87页。302.快速快速(kui s)排序排序(Quick Sort)基本基本(jbn)(jbn)思想思想 根据选定的支点根据选定的支点L，通过一趟排序将待排记录，通过一趟排序将待排记录(jl)分割成独立的两部分，其中一部分记录分割成独立的两部分，其中一部分记录(jl)的关键字均小于的关键字均小于L，而另一部分记录，而另一部分记录(jl)的关键字均大于等于的关键字均大于等于L。分别对这两部分记录。分别对这两部分记录(jl)继续进行排序，

31、以达到整个序列有序继续进行排序，以达到整个序列有序。支点的选择方法支点的选择方法 取第一个记录；最后一个记录；第一个、最后一个和取第一个记录；最后一个记录；第一个、最后一个和中间记录三者中，关键字居中的那个记录。中间记录三者中，关键字居中的那个记录。第29页/共87页第三十页，共87页。31 具体做法具体做法 设待排序的序列设待排序的序列(xli)为为rs，rs+1，rt。附设。附设两个指针两个指针i和和j，它们的初值分别为，它们的初值分别为s和和t，设支点记录，设支点记录pivot=rs，x=pivotkey。则首先从。则首先从j所指位置起向前搜索找到第所指位置起向前搜索找到第一个关键字小于

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

33、23 37 33 47 43 i i j 快速排序快速排序第31页/共87页第三十二页，共87页。332次次 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快速快速(kui s)排序排序第32页/共87页第三十三页，共87页。345次次 35 41 33 33 37 23 43 74 47 67 i j j快速快速(kui s)排序排序5次次 35 41 33 33 37 23 43 74 47 67 i j完成完成

34、(wn chng)一趟一趟 35 41 33 33 37 23 43 74 47 67第33页/共87页第三十四页，共87页。35快速排序快速排序(pi x)的算法的算法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页第三十五页，共

35、87页。36int Partition(SqList&L,int low,int high)L.r0=L.rlow;int pivotkey=L.rlow.key;while(low 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页第三十六页，共87页。37 算法算法算法算法(sun f)(sun f)分析分析分析分析n n从快速排序算法的递归树可知，快速排序的趟数取决于递归树的从快

36、速排序算法的递归树可知，快速排序的趟数取决于递归树的从快速排序算法的递归树可知，快速排序的趟数取决于递归树的从快速排序算法的递归树可知，快速排序的趟数取决于递归树的深度。深度。深度。深度。n n如果如果如果如果(rgu)(rgu)每次划分对一个对象定位后，该对象的左侧子序列与每次划分对一个对象定位后，该对象的左侧子序列与每次划分对一个对象定位后，该对象的左侧子序列与每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列右侧子序列的长度相同，则下一步将是对两个长度减半的子序列右侧子序列的长度相同，则下一步将是对两个长度减半的子序列右侧子序列的长度相

37、同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。进行排序，这是最理想的情况。进行排序，这是最理想的情况。进行排序，这是最理想的情况。n n在在在在n n个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为个元素的序列中，对一个对象定位所需时间为 O(n)O(n)。若设。若设。若设。若设 t(n)t(n)是对是对是对是对 n n 个元素的序列进行排序所需的时间，而且每次对一个对象个元素的序列进行排序所需的时间，而且每次对一个对象个元素的序列进行排序所需的时间，而且每次对一个对象个元素的序列进行排序所需的时间，而

38、且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，正确定位后，正好把序列划分为长度相等的两个子序列，此时，正确定位后，正好把序列划分为长度相等的两个子序列，此时，正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：总的计算时间为：总的计算时间为：总的计算时间为：第36页/共87页第三十七页，共87页。38T(n)T(n)cn+2 t(n/2)cn+2 t(n/2)/c /c是一个常数是一个常数是一个常数是一个常数 Cn+2(cn/2+2t(n/4)=2cn+4t(n/4)Cn+2(cn/2+2t(n/4)=2cn+4t(n/4)2cn+4(cn/4+2

39、t(n/8)=3cn+8t(n/8)2cn+4(cn/4+2t(n/8)=3cn+8t(n/8)Cn log2n+nt(1)=o(n log2n)Cn log2n+nt(1)=o(n log2n)可可可可以以以以证证证证明明明明，函函函函数数数数quicksortquicksort的的的的平平平平均均均均计计计计算算算算时时时时间间间间也也也也是是是是o(nlog2n)o(nlog2n)。实实实实验验验验结结结结果果果果表表表表明明明明：就就就就平平平平均均均均计计计计算时间而言，快速算时间而言，快速算时间而言，快速算时间而言，快速(kui s)(kui s)排序是我们所讨论的所有内排序方法中

40、最好的一个。排序是我们所讨论的所有内排序方法中最好的一个。排序是我们所讨论的所有内排序方法中最好的一个。排序是我们所讨论的所有内排序方法中最好的一个。第37页/共87页第三十八页，共87页。39n n快快快快速速速速排排排排序序序序是是是是递递递递归归归归的的的的，需需需需要要要要有有有有一一一一个个个个栈栈栈栈存存存存放放放放每每每每层层层层递递递递归归归归调调调调用用用用时时时时的的的的指指指指针和参数。针和参数。针和参数。针和参数。n n最最最最大大大大递递递递归归归归调调调调用用用用层层层层次次次次数数数数与与与与递递递递归归归归树树树树的的的的深深深深度度度度一一一一致致致致，理理理

41、理想想想想情情情情况况况况为为为为 log2(n+1)log2(n+1)。因此，要求存储开销为。因此，要求存储开销为。因此，要求存储开销为。因此，要求存储开销为 o(log2n)o(log2n)。n n在在在在最最最最坏坏坏坏的的的的情情情情况况况况，即即即即待待待待排排排排序序序序对对对对象象象象序序序序列列列列已已已已经经经经按按按按其其其其关关关关键键键键字字字字从从从从小小小小到到到到大大大大排排排排好好好好序序序序的的的的情情情情况况况况下下下下，其其其其递递递递归归归归树树树树成成成成为为为为单单单单支支支支树树树树，每每每每次次次次划划划划分分分分(hu(hu fn)fn)只只只

42、只得得得得到到到到一一一一个个个个比比比比上上上上一一一一次次次次少少少少一一一一个个个个对对对对象象象象的的的的子子子子序序序序列列列列。这这这这样样样样，必必必必须须须须经经经经过过过过 n-1 n-1 趟趟趟趟才才才才能能能能把把把把所所所所有有有有对对对对象象象象定定定定位位位位，而而而而且且且且第第第第 i i 趟趟趟趟需需需需要要要要经经经经过过过过 n-i n-i 次次次次关关关关键键键键字字字字比比比比较较较较才才才才能能能能找找找找到到到到第第第第 i i 个个个个对对对对象象象象的的的的安安安安放放放放位位位位置置置置，总总总总的的的的关关关关键键键键字字字字比比比比较较较

43、较次次次次数将达到数将达到数将达到数将达到第38页/共87页第三十九页，共87页。40其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储其排序速度退化到简单排序的水平，比直接插入排序还慢。占用附加存储(即栈即栈即栈即栈)将达到将达到将达到将达到o(n)o(n)。若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。若能更合理地选择基准对象，使得每次划分所得的

44、两个子序列中的对象个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。若能更合理地选择基准对象，使得每次划分所得的两个子序列中的对象个数尽可能地接近，可以加速排序速度，但是由于对象的初始排列次序是随机的，这个要求很难办到。有一种有一种有一种有一种(y zhn)(y zhn)改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接

45、近正中的改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3 3个对象，取其关键字居中者作为基准对象。个对象，取其关键字居中者作为基准对象。个对象，取其关键字居中者作为基准对象。个对象，取其关键字居中者作为基准对象。快速排序是一种快速排序是一种快速排序是一种快速排序是一种(y zhn)(y zhn)不稳定的排序方法。不稳定的排序方法。不稳定的排序方法。不稳定的排序方法。对于对于对于对于 n n 较大的平均情况而言，快速排序是较大的平均情况而言，快速排序是较大的平均情况而言，快速排序是较大的平均情况而言

46、，快速排序是“快速快速快速快速”的，但是当的，但是当的，但是当的，但是当 n n 很小时，这种排序方法往往比其它简单排序方法还要慢。很小时，这种排序方法往往比其它简单排序方法还要慢。很小时，这种排序方法往往比其它简单排序方法还要慢。很小时，这种排序方法往往比其它简单排序方法还要慢。第39页/共87页第四十页，共87页。41 基本基本(jbn)思想思想 每一趟在每一趟在 n-i+1（i=1，2，n-1）个记录中选取）个记录中选取(xunq)关关键字最小的记录作为有序序列中第键字最小的记录作为有序序列中第 i 个记录。个记录。分类分类(fn li)简单选择排序简单选择排序 树形选择排序树形选择排序

47、 堆排序堆排序10.4 10.4 选择排序选择排序选择排序选择排序第40页/共87页第四十一页，共87页。421.简单简单(jindn)选择排选择排序序2.(Simple Selection Sort)基本基本(jbn)思想思想 通过通过 n-i次关键字间的比较，从次关键字间的比较，从 n-i+1个记录个记录(jl)中选出关中选出关键字最小的记录键字最小的记录(jl)，并和第，并和第i（1 i n）个记录）个记录(jl)交换之（称为交换之（称为一趟简单选择排序）。具体实现时令一趟简单选择排序）。具体实现时令 i 从从1至至n-1，进行，进行n-1次选择操作。次选择操作。第41页/共87页第四十

48、二页，共87页。43 算法算法(sun f)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;简单选择简单选择(xunz)排序排序第42页/共87页第四十三页，共87页。44简单选择简单选择(xunz)排序排序 举例举例(j l)4938659776132749初始(ch sh)关键字1338659776492749第一趟排序后1327659776493849第二趟排序后1

49、327389776496549第三趟排序后1327384976976549第四趟排序后1327384949976576第五趟排序后1327384949659776第六趟排序后1327384949657697第七趟排序后第43页/共87页第四十四页，共87页。45 算法算法算法算法(sun f)(sun f)分析分析分析分析n n直接选择排序的关键字比较直接选择排序的关键字比较次数次数KCN与对象的初始与对象的初始(ch sh)排列无关。第排列无关。第 i 趟趟选择具有最小关键字对象所选择具有最小关键字对象所需的比较次数总是需的比较次数总是 n-i-1 次，次，此处假定整个待排序对象序此处假定整

50、个待排序对象序列有列有 n 个对象。因此，总的个对象。因此，总的关键字比较次数为关键字比较次数为第44页/共87页第四十五页，共87页。46n n对象的移动次数与对象序列的初始排列有关。对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小当这组对象的初始状态是按其关键字从小到大有序的时候，对象的移动次数到大有序的时候，对象的移动次数RMN=0，达到，达到(d do)最少。最少。n n最坏情况是每一趟都要进行交换，总的对象最坏情况是每一趟都要进行交换，总的对象移动次数为移动次数为RMN=3(n-1)。n n直接选择排序是一种不稳定的排序方法。直接选择排序是一种不稳定的排序