第9章排序--1.ppt

1、第九章排序讲座：顾(1)，第九章排序目录9.1排序概述9.2插入排序9.3交换排序9.4选择排序9.5合并排序9.6基数排序，9.1排序概述，操作对象：同类型数据元素集合。操作目标：根据键值将数据元素的无序序列排列成有序序列。稳定排序和不稳定排序：假设：Ri.key=Rj.key假设Ri在排序之前排列在Rj之前；排序后，如果Ri仍然排列在Rj之前，这是一个稳定的排序算法；如果不能保证，这是一个不稳定的排序算法。内部排序和外部排序：内部排序-所有要排序的记录都存储在内存中；外部排序-一部分在内存中，另一部分在外部内存中。在分类过程中，内部和外部存储器之间有数据交换。排序的基本动作：比较移动排序性

2、能的评估：比较时间和移动时间的评估，排序方法：插入排序、直接插入排序、分割插入排序、双向插入排序、希尔排序、交换排序、气泡排序、快速排序、简单选择排序、堆排序、树选择排序、合并排序、双向合并排序、基数排序、高级排序算法：时间复杂度-o (nlogn)通用排序算法时间复杂度-o (N2)， 第十章排序目录9.1排序概述9.2插入排序9.3交换排序9.4选择排序9.5合并排序9.6基数排序，9.2插入排序，9.2.1直接插入排序9.2.2半插入排序9.2.3双向插入排序9.2.4希尔排序，直接插入排序算法的思想：排序区间r 1 .n；在排序过程中，整个排序区间被分为两个子区间：有序区域R1.-1和

3、无序区.n。总共执行n1个排序过程，并且每个排序过程将无序区域中的第一记录Ri插入有序区域中的适当位置。在有n个元素的有序序列表l中插入一个新元素e，这样l仍然是有序的：对于(I=n-1；I=0，初始状态：有序区域是R1，58，15，46，45，90，08，32，r，岗哨，15，58，r，46，45，90，08，32，第一遍，I2；1558，15分配到监视岗位；有序区域中所有大于15的记录向右移动一位，并将15放入空出的空间。初始状态为：46，R，第二遍，I3；4658，46分配到监视岗位；有序区域中所有大于46的记录向右移动一位，并将46放入空出的空间15，58，初始状态：在第一次行程之后：

4、R，90，08，32，第三次行程，i4；4558，45分配到监视岗位；有序区域中所有大于45的记录向右移动一个位置，并将45放入空出的空间，15，45，58，46，初始状态：第一次行程之后：第二次行程之后：第四次行程，i5；9058，没有移动发生；90，初始状态：第一次行程后：第二次行程后：第三次行程后：第五次行程后，I6；R，08，15，45，46，58，90，初始状态：第一次行程后：第二次行程后：第三次行程后：第四次行程后：第六次行程后，i7；r，08，15，32，45，46，58，90，初始状态：第一遍后：第二遍后：第三遍后：第四遍后：第五遍后：存储结构-以顺序存储结构为例InfoTyp

5、eotherinfo记录类型；Typedef结构/排序表类型RecordTyperMaxSize 1；intlengthSqList。直接插入排序算法：void insert short(sqlist/将ri放在有序区域的正确位置/end if，R0有两个功能：保持R i的复制哨兵，并监视j是否越界。直接插入排序的性能分析：最佳情况：表的初始状态恰好为正顺序，比较次数：移动次数：Mmin0最差情况：表的初始状态恰好为反顺序，比较次数：平均比较次数：平均移动次数：时间复杂度：O(n2)，直接插入排序是一种稳定的排序方法，9.2插入排序，9.2.1直接插入排序9.2.2半插入排序9.2.3双向插入

6、排序9.2.4希尔排序， 双向插入排序：在表的两端执行插入操作，这可以将平均移动路径减少一半。 49、38、97、65、76、13、27、和双向插入排序：在表的两端执行。97、D、38、49、双向插入排序：插入操作在表的两端执行，这可以将平均移动路径减少一半，49、38、97、65、76、13、27、R、49、65、97、97，65，76，13，27，R，49，65，76，97，D，38，49，双向插入排序3360在表的两端执行，这可以将平均移动路径减少一半，49，38，97，65，65双向插入排序：在表的两端执行，这可以将平均移动路径减少一半，49，38，97，65，76，13 76，97，

7、13，d，38，49，27，9.2插入排序，9.2.1直接插入排序9.2.2半插入排序9.2.3双向插入排序9.2.4表格插入排序9希尔排序就是基于这两点来改进直接插入排序的。希尔排序又称收缩增量排序，希尔排序算法的思想是：在排序过程中，将整个排序区间分成若干个子表；直接插入并排序每个子表，因为n2n12n2nk2 (n=n1n2nk)，排序每个子表所花费的时间总和小于排序整个间隔所花费的时间。通过在小范围内对子表进行排序，排序间隔被调整为基本有序的序列。不断减少子表的数量(即扩展子表的长度)，直到子表的数量为1，完成整个排序操作。子表不是连续划分的，而是以一定的增量dk记录，然后逐渐减少这个

8、增量，直到dk1。Dk=3 R1，R2，R3，R4，R5，R6，R7，R8，R9，R10子表1: R1 R4 R7 R10子表23360R2R5R8子表：R3 R6 R9，例如：希尔排序，递增顺序是5，3，1，DK=5:9，4，3 7，2，6，4，8，6，5，1，DK=:4，2，4，3第十章排序目录9.1排序概述9.2插入排序9.3交换排序9.4选择排序9.5合并排序9.6基本排序，交换排序概述交换排序的基本思想是：比较两个记录Ri和Rj (IRj。关键-逆序排列，然后交换Ri和RJ的立场是不同的，根据方式Ri和RJ采取。它可以分为冒泡排序和快速排序，Ri，Rj，9.3交换排序，9.3.1冒泡

9、排序，9.3.2快速排序和9.3.1冒泡排序从下到上(或从上到下)扫描记录序列，两个相邻的记录Ri和Ri 1(或Ri1)交换位置，如果它们的顺序相反。67，45，51，21，33，45，12，45，67，21，58，51，12，33，45，第二趟，58，67，51，45，33，45，21，12，45，45，21，12，45，67，21，58，51，12，33，45，第二趟，58，67，51，45，33，12，21，51，45，67，67，45，67，21，58，51，12，33，45，第二次行程，58，12，33，21，45，45，51，67，45，67在第三次行程中，58，12，21，33，

10、51，45，45，类似地，在第四次行程中没有发生移动，表明所有的记录都已经排序，并且算法可以结束，气泡分类性能分析：最佳情况：表的初始状态恰好按正顺序排列，并且在第一次扫描中没有移动。比较时间：Cminn移动时间：Mmin0最坏的情况：表的初始状态恰好以相反的顺序排列，需要排序n-1次。每次，整个间隔都应该被移动。比较时间：移动时间：同等条件下的平均情况：平均比较时间：平均移动时间。时间复杂度：0(N2)，冒泡排序是一种稳定的排序方法，9.3交换排序，9.3.1冒泡排序，9.3.2快速排序，9.3.2快速排序是一种快速排序算法。快速排序认为排序间隔是R低.高；在排序间隔中选择任意记录Rx作为参

11、考；在排序一次后，排序间隔被分为左和右子间隔：右低.i-1 Rx R i 1.高，所以其余低.I-1。钥匙rx。钥匙R1.很高。键，然后用相同的方法对左右间隔进行排序，直到每个间隔的长度为1。45，67，21，58，51，12，33，45，基准，初始状态：低=1，高=n；以区间的第一个元素为基准；两个指针I和j设置在间隔的两端，并且两个指针交替地向中间扫描；首先，指针J向左扫描，当遇到键值小于引用的记录r J时，它将交换rjj；一次。然后指针向右扫描，当键值大于参考记录Ri时，指针交换RiRj一次；当两个指针相遇时，分区结束。、45、67、21、58、51、1 2、33、45，第一分区、45、

12、45、58、12、51、67、33、21、33、21、45、45、58、33、12、67、21，第一分区、第二分区、51、45、58、12、51、67、31、51、21，第三分区、51、21分区算法(P274，算法9.6a)内部分区(SqList /交换基准返回I；/返回基准的位置索引，这也可以改进划分算法：基准临时存储在L.R0位置，在划分过程中基准不移动，只在一个方向上移动，即通过L . R i或L.RJ.当隔板结束时，将基准移动到正确的位置。1.分区算法的改进(P274，算法9.6b)内部分区(SqList /就地基准返回I；/返回基准的位置指数，2。快速排序低的右半部分.高间隔快速排序

13、(P276，算法9.7) void QSort(SqList /)，3。使用快速排序(P276，算法9.8)对整个序列表进行快速排序。无效快速排序(SqList，快速排序的性能分析：最坏情况：表的初始状态恰好是正序列。每次划分时，基准恰好是间隔的最大或最小键值。作为分区的结果，有一个：的空间隔。对于初始状态按正序或逆序排列的表，您需要进行n1次排序，每次需要比较：次。快速排序退化为冒泡排序，时间复杂度达到0(N2)。最好的情况是，每次划分时，基准恰好是区间的中间值。作为分区的结果，让我们设置表长度n2k，并使用C(m)来表示对长度为m的表进行排序所需的比较次数：cmin=C(n)n2c(n/2)N2(n/22c(n/22)=2n 22c(n/22)2n 22(n/222c(n/23)快