《数据结构 第十章 内部排序》由会员分享，可在线阅读，更多相关《数据结构 第十章 内部排序（117页珍藏版）》请在金锄头文库上搜索。
1、1,第十章内 部 排 序,2,1. 了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和基数排序等五类。,学习目标,本章讨论比较内部各种排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想，算法特点，排序过程以及它们的时间复杂度分析。在每类排序方法中，从简单方法入手，重点讨论性能先进的高效方法（如，插入排序类中的希尔排序，交换排序类中的快速排序，选择排序类中的堆排序等）。通过本章学习，要求同学们：,3,2. 掌握各种排序方法的时间复杂度的分析方法。
2、能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。,3理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。,4. 了解外部排序的基本过程及其时间分析。,4,9.1 概 述,一、排序的定义,二、内部排序和外部排序,三、内部排序方法的分类,5,一、什么是排序？,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,6
3、,一般情况下，假设含n个记录的序列为 R1,R2, ， Rn 其相应的关键字序列为 K1,K2, ，Kn ,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为 ： Rp1, Rp2, ，Rpn 的操作称作排序。,7,二、内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。,8,三、内部排序的方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序
4、列 区,有序序列区,无 序 序 列 区,9,基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,10,待排记录的数据类型定义如下:,#define MAXSIZE 1000 /待排顺序表最大长度,typedef int KeyType; / 关键字类型为整数类型,typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型,typedef struct RcdType rMAXSIZE+1; /r0闲置 int length; /顺序
5、表长度 SqList; /顺序表类型,11,1. 插入类,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,12,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将加入到有序子序列中，以此方法增加记录的有序子序列的长度。,13,3. 选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,14,4. 归并类,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,5. 其它方法,15,9. 2插 入 排 序,16,有序序列R1.i-1,Ri,
6、无序序列 Ri.n,一趟直接插入排序的基本思想：,有序序列R1.i,无序序列 Ri+1.n,17,实现“一趟插入排序”可分三步进行：,3将Ri 插入(复制)到Rj+1的位置上。,2将Rj+1.i-1中的所有记录均后移一个 位置；,1在R1.i-1中查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；,18,直接插入排序（基于顺序查找）,表插入排序（基于链表存储）,不同的具体实现方法导致不同的算法描述,折半插入排序（基于折半查找）,希尔排序（基于逐趟缩小增量）,19,一、直接插入排序,利用“顺序查找”实现“在R1.i-1 中查找Ri的插入位置”,算法的实现要点：,20
7、,从Ri-1起向前进行顺序查找，监视哨设置在R0；,R0 = Ri; / 设置“哨兵”,循环结束表明Ri的插入位置为 j +1,R0,j,Ri,for (j=i-1; R0.keyRj.key; -j); / 从后往前找,j=i-1,插入位置,21,对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,22,令 i = 2，3，, n,实现整个序列的排序。,for ( i=2; i=n; +i ) i
8、f (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; ,23,void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.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; / 插入到正确位置,24,内部排序的时间分析：,实现内部排序的基本操作有
9、两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的大小；,25,对于直接插入排序：,最好的情况（关键字在记录序列中顺序有序）,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,26,因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。,二、折半插入排序,27,void BiInsertionSort ( SqList &L ) / BInsertSort,/在 L.r1.i-1中折半查找插入位置；,for ( i=2; i
10、=high+1; -j ) L.rj+1 = L.rj; / 记录后移,L.rhigh+1 = L.r0; / 插入,28,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;/插入点在高半区,29,14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 61 80,23 97 75,i,low,high,m,high
11、,m,high,m,low,例如:,再如:,插入位置,插入位置,L.r,L.r,30,三、表插入排序,为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。,31,void LInsertionSort (Elem SL ， int n) / 对记录序列SL1.n作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0, k = SL0.ne
12、xt;SLk.key= SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 结点i插入在结点j和结点k之间/ LinsertionSort,32,算法中使用了三个指针：其中： p指示第i个记录的当前位置 i指示第i个记录应在的位置 q指示第i+1个记录的当前位置,如何在排序之后调整记录序列？,33,void Arrange ( Elem SL , int n ) p = SL0.next; /p指示第一个记录的当前位置 for ( i=1; in; +i ) while (pi) p = SLp.next; q = SLp.nex
13、t; / q指示尚未调整的表尾 if ( p!= i ) SLpSLi; /交换记录，使第i个记录到位 SLi.next = p; / 指向被移走的记录 p = q; / p指示尚未调整的表尾， / 为找第i+1个记录作准备 / Arrange,34,四、希尔排序（又称缩小增量排序）,基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是，“跳跃式”的插入排序。 具体做法为：,35,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d,
