《数据结构(严蔚敏)课件第10章》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)课件第10章（119页珍藏版）》请在金锄头文库上搜索。
1、2019年6月13日星期四,第1页,第十章 排序,2019年6月13日星期四,第2页,【课前思考】,在第一章中曾以选择排序和起泡排序为例讨论算法实践复杂度，不知你还记得吗？,2019年6月13日星期四,第3页,【学习目标】,1理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较“进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。 2掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数“分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O (n2)
2、 的简单排序方法，O (nlogn) 的高效排序方法和O (dn)的基数排序方法。 3理解排序方法“稳定“或“不稳定“的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。,2019年6月13日星期四,第4页,【重点和难点】,希尔排序、快速排序、堆排序和归并排序等高效方法是本章的学习重点和难点。,【知识点】,排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较 。,2019年6月13日星期四,第5页,【学习指南】,本章学习的要点主要是了解各种排序方法实现时所依据的原则以及它们的主要操作（“关键字间的比
3、较”和“记录的移动”）的时间分析。学习中应注意掌握各种排序方法实现的要点，可通过对基础知识题中算法的手工执行和比较分析，切实掌握各种排序过程的排序特点所在，注意同一排序方法在不同的教科书上可以有不同书写形式描述的算法。在学习本章过程中需练习的算法设计题为：10.23，10.25，10.27 ， 10.32， 10.34， 10.38, 10.42 和 10.45。,2019年6月13日星期四,第6页,10.1 概述,10.2 插入排序,10.3 快速排序,10.4 堆排序,10.5 归并排序,10.6 基数排序,10.7 各种排序方法的综合比较,10.8 外部排序,2019年6月13日星期四,
4、第7页,10.1 概 述,一、排序的定义,二、内部排序和外部排序,三、内部排序方法的分类,2019年6月13日星期四,第8页,一、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,2019年6月13日星期四,第9页,一般情况下， 假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn ,这些关键字相互之间可以进行
5、比较，即在 它们之间存在着这样一个关系 ： Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,2019年6月13日星期四,第10页,二、内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序。,2019年6月13日星期四,第11页,三、内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,2019年6月13日星
6、期四,第12页,基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,2019年6月13日星期四,第13页,待排记录的数据类型定义如下:,#define MAXSIZE 1000 / 待排顺序表最大长度,typedef int KeyType; / 关键字类型为整数类型,typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型,typedef struct RcdType rMAXSIZE+1; / r0闲置 int length;
7、 / 顺序表长度 SqList; / 顺序表类型,2019年6月13日星期四,第14页,1. 插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,2019年6月13日星期四,第15页,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,2019年6月13日星期四,第16页,3. 选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,2019年6月13日星期四,第17页,4. 归并类,通过“归并”
8、两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,5. 其它方法,2019年6月13日星期四,第18页,10. 2 插 入 排 序,2019年6月13日星期四,第19页,有序序列R1i-1,Ri,无序序列 Rin,一趟直接插入排序的基本思想：,有序序列R1i,无序序列 Ri+1n,2019年6月13日星期四,第20页,实现“一趟插入排序”可分三步进行：,3将Ri 插入(复制)到Rj+1的位置上。,2将Rj+1i-1中的所有记录均后移 一个位置；,1在R1i-1中查找Ri的插入位置， R1j.key Ri.key Rj+1i-1.key；,2019年6月13日星期四,第21页,直接插
9、入排序（基于顺序查找）,表插入排序（基于链表存储）,不同的具体实现方法导致不同的算法描述,折半插入排序（基于折半查找）,希尔排序（基于逐趟缩小增量）,2019年6月13日星期四,第22页,一、直接插入排序,利用 “顺序查找”实现 “在R1i-1中查找Ri的插入位置”,算法的实现要点：,2019年6月13日星期四,第23页,从Ri-1起向前进行顺序查找， 监视哨设置在R0；,R0 = Ri; / 设置“哨兵”,循环结束表明Ri的插入位置为 j +1,R0,j,Ri,for (j=i-1; R0.keyRj.key; -j); / 从后往前找,j=i-1,插入位置,2019年6月13日星期四,第2
10、4页,对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,2019年6月13日星期四,第25页,令 i = 2，3，, n, 实现整个序列的排序。,for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1i-1中查找Ri的插入位置; 插入Ri ; ,2019年6月13日星期四,第26页,void InsertionSort ( SqList +i ) if (L.r
11、i.key L.ri-1.key) / InsertSort,L.r0 = L.ri; / 复制为监视哨 for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / 插入到正确位置,2019年6月13日星期四,第27页,内部排序的时间分析：,实现内部排序的基本操作有两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的 大小；,2019年6月13日星期四,第28页,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）：,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）：,“比
12、较”的次数：,0,“移动”的次数：,“移动”的次数：,2019年6月13日星期四,第29页,因为 R1i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。,二、折半插入排序,2019年6月13日星期四,第30页,void BiInsertionSort ( SqList &L ) / BInsertSort,在 L.r1i-1中折半查找插入位置；,for ( i=2; i=L.length; +i ) / for,L.r0 = L.ri; / 将 L.ri 暂存到 L.r0,for ( j=i-1; j=high+
13、1; -j ) L.rj+1 = L.rj; / 记录后移,L.rhigh+1 = L.r0; / 插入,2019年6月13日星期四,第31页,low = 1; high = i-1; while (low=high) ,m = (low+high)/2; / 折半,if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区 else low = m+1; / 插入点在高半区,2019年6月13日星期四,第32页,14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 6
14、1 80,23 97 75,i,low,high,m,high,m,high,m,low,例如:,再如:,插入 位置,插入 位置,L.r,L.r,2019年6月13日星期四,第33页,三、表插入排序,为了减少在排序过程中进行的 “移动”记录的操作，必须改变排序过 程中采用的存储结构。利用静态链表 进行排序，并在排序完成之后，一次 性地调整各个记录相互之间的位置， 即将每个记录都调整到它们所应该在 的位置上。,2019年6月13日星期四,第34页,void LInsertionSort (Elem SL ， int n) / 对记录序列SL1n作表插入排序 SL0.key = MAXINT ;
15、SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 结点i插入在结点j和结点k之间 / LinsertionSort,2019年6月13日星期四,第35页,算法中使用了三个指针： 其中：p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置,如何在排序之后调整记录序列？,2019年6月13日星期四,第36页,void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一个记录的当前位置 for ( i=1; in; +i ) while (pi) p
