数据结构 ch10 排序课件

王秀章王秀章 2005.82007.4物理系物理系 数据结构排序数据结构 ch10 排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲第十章第十章 排序排序10.1概述概述10.2 插入排序插入排序10.3 交换排序交换排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲10.1概述概述一、什么是排序？一、什么是排序？二、内部排序和外部排序二、内部排序和外部排序三、内部排序的方法三、内部排序的方法湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲10.1概述概述排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。 一、什么是排序？一、什么是排序？例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲一般情况下，假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Kp1Kp2Kpn按此固有关系将式(1)的记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲二、内部排序和外部排序二、内部排序和外部排序 在本章内先讨论内部排序的各种方法，然后介绍外部排序的基本过程。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲三、内部排序的方法三、内部排序的方法有序序列区 无序序列区内部排序的过程是一个逐步扩大记录的有序内部排序的过程是一个逐步扩大记录的有序序列长度的过程序列长度的过程。在排序的过程中，参与排序的。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。记录序列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操使有序区中记录的数目增加一个或几个的操作称为作称为一趟排序一趟排序。有 序 序 列 区 无 序 序 列 区湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲1.1.插入类插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；逐步扩大记录有序序列长度的方法大致逐步扩大记录有序序列长度的方法大致有下列几类：有下列几类：2.2.交换类交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲3.3.选择类选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;4. 4. 归并类归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;5.5.其它方法其它方法下面将对每一类的排序算法介绍一至两个排序算法。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲有序序列R1.i-1无序序列 Ri.nRi假设在排序过程中，记录序列R1.n的状态为：有序序列R1.i无序序列 Ri+1.n则一趟直接插入排序的基本思想为：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。10.2 插入排序插入排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲显然，完成这个“插入”需分三步进行：2将Rj+1.i-1中的记录后移一个位置；3将Ri复制到Rj+1的位置上。1查找Ri的插入位置j+1；R1.j Ri Rj+1.i-1湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲一、直接插入排序一、直接插入排序二、折半插入排序二、折半插入排序三、希尔排序三、希尔排序10.2 插入排序插入排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲一、直接插入排序一、直接插入排序利用顺序查找实现“在R1.i-1中查找Ri的插入位置”的插入排序。 排序过程： 整个排序过程为i-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲算法实现的要点：1.1.从Ri-1起向前进行顺序查找,监视哨设置在R0; R0 = Ri; / 设置“哨兵” for (j=i-1; R0.keyRj.key; -j); / 从后往前找 return j+1; / 返回Ri的插入位置为j+12.2.对于在查找过程中找到的那些关键字不小于Ri.key的记录，可以在查找的同时实现向后移动； for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj3. 3. i = 2，3，, n, 实现整个序列的排序。for (i=2; i=2; +i); if(Ri.keyRi-1.key) 将Ri插入到= R1.i-1中 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void InsertionSort ( Elem R , int n) / 对记录序列R1.n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 复制为监视哨 for ( j=i-1; R0.key Rj.key; -j ) Rj+1 = Rj; / 记录后移 Rj+1 = R0; / 插入到正确位置 / InsertSort算法描述：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲（1）“比较比较”序列中两个关键字的大小序列中两个关键字的大小；时间分析：时间分析：实现排序的基本操作有两个：实现排序的基本操作有两个：（2）“移动移动”记录。记录。 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲112nni2)1)(2(2nnini2)1)(4()1(2nnini最好的情况：最好的情况： 若待排序记录按关键字从小到大排列若待排序记录按关键字从小到大排列( (正序正序) )关键字“比较”次数：最坏的情况：最坏的情况： 若待排序记录按关键字从大到小排列若待排序记录按关键字从大到小排列( (逆序逆序) )对于直接插入排序：对于直接插入排序：记录“移动”次数：0记录“移动”次数：关键字“比较”次数：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲42n42nT(n)=O(n)若待排序记录是随机的，取平均值若待排序记录是随机的，取平均值关键字“比较”次数：记录“移动”次数：空间复杂度：时间复杂度：S(n)=O(1)湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲因为R1.i-1是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。 二、折半插入排序二、折半插入排序排序过程： 用折半查找方法确定插入位置的排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void BiInsertionSort (Elem R ， int n) / 对记录序列R1.n作折半插入排序。 for ( i=2; i=L.length; +i ) R0 = Ri; / 将Ri暂存到R0 low = 1; high = i-1;while (low=high) /在Rlow.high中折半查找插入的位置 m = (low+high)/2; / 折半 if (R0.key =high+1; -j ) Rj+1 = Rj; / 记录后移 Rhigh+1 = R0; / 插入 / BInsertSort湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度：T(n)=O(n)q空间复杂度：S(n)=O(1)折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲三、希尔排序三、希尔排序(缩小增量法缩小增量法)基本思想：对待排记录系列，先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是“跳跃式”的插入排序。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲其中d为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。具体做法为：将记录系列分成若干个子系列，分别对每个子系列作插入排序。R1, R1+d, R1+2d, ,R1+kdR2, R2d, R3d, , R(k+1)d R2, R2+d, R2+2d, ,R2+kd湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲取d3=1三趟分组：13 4 48 38 27 49 55 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始： 49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 76湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲Ch8_3.c例49 38 65 97 76 13 27 48 55 4ji49133827一趟排序：13 27 48 55 4 49 38 65 97 76jiji274jiji55ji38jijiji二趟排序： 13 4 48 38 27 49 55 65 97 76jiji6548ji9755ji764湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲算法描述：void ShellInsert(SqList &L,int dk) / 对顺序表L作一趟希尔插入排序。 int i,j; for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk) L.rj+dk=L.rj; / 记录后移，查找插入位置 L.rj+dk=L.r0; / 插入 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 void ShellSort(SqList &L,int dlta,int t) / 按增量序列dlta0.t-1对顺序表L作希尔排序。 int k; for(k=0;k1) lastexchangeIndex=1; for(j=1; jAj+1) Swap(Aj,Aj+1); lastexchangeIndex=j; /if i=lastexchangeIndex; /while /bubble_sort起泡排序的结束条件为：最后一趟没有进行最后一趟没有进行“交换交换”。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度最好情况（正序） 只需进行一趟起泡Y比较次数：n-1Y移动次数：0最坏情况（逆序）需进行n-1趟起泡Y比较次数：) 1(21)(21nninniY移动次数：) 1(23)(321nninniq空间复杂度：S(n)=O(1)T(n)=O(n)湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该记录之前移动至该记录之前，反之，凡关键字大关键字大于枢轴于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分割成两部分：分割成两部分：Rs.i-1和和Ri+1.t,且且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)二、一趟快速排序二、一趟快速排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例如例如: :关键字序列52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证Rhigh.key52，而Rlow.key52,否则进行记录的“交换”。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始关键字： 49 38 65 97 76 13 27 50 lhxhl 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 4927lhlhlh4965hl1349lh4997lh湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲int Partition(SqList &L,int low,int high) / 交换顺序表L中子表L.rlow.high的记录，使枢轴记录到位， / 并返回其所在位置，此时在它之前(后)的记录均不大(小)于它。算法10.6(a) RedType t; KeyType pivotkey; pivotkey=L.rlow.key; / 用子表的第一个记录作枢轴记录 while(lowhigh) / 从表的两端交替地向中间扫描 while(low=pivotkey) -high; t=L.rlow; / 将比枢轴记录小的记录交换到低端 L.rlow=L.rhigh; L.rhigh=t; while(lowhigh&L.rlow.key=pivotkey) +low; t=L.rlow; / 将比枢轴记录大的记录交换到高端 L.rlow=L.rhigh; L.rhigh=t; return low; / 返回枢轴所在位置 算法描述算法描述湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。三、快速排序三、快速排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲快速排序的算法描述如下:void QSort (Elem R, int low, int high) / 对记录序列Rlow.high进行快速排序 if (low high-1) / 长度大于1 pivotloc = Partition(L, low, high); / 将L.rlow.high一分为二 QSort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 / QSort湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void QuickSort(Elem R, int n) / 对记录序列进行快速排序 QSort(R, 1, n); / QuickSort湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲q时间复杂度最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n)v空间复杂度：需栈空间以实现递归l最坏情况：S(n)=O(n)l一般情况：S(n)=O(log2n)vT(n)=O(n)四、快速排序的时间分析四、快速排序的时间分析湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲一、简单选择排序一、简单选择排序二、堆排序二、堆排序10.4 选择排序选择排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲一、简单选择排序一、简单选择排序假设排序过程中，待排记录序列的状态为： 无序序列 Ri.n有序序列R1.i-1从中选出关键字最小的记录加入有序序列。第i趟简单选择排序是有序序列R1.i无序序列 Ri+1.n有序序列中所有记录的关键字均小于无序序列中记录的关键字湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序结束： 13 27 38 49 65 76 97湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void SelectSort(SqList &L) / 对顺序表L作简单选择排序。 int i,j; RedType t; for(i=1;iL.length;+i) / 选择第i小的记录，并交换到位 j=SelectMinKey(L,i); / 在L.ri.L.length中选择key最小的记录 if(i!=j) / 与第i个记录交换 t=L.ri; L.ri=L.rj; L.rj=t; 算法描述算法描述湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度记录移动次数Y最好情况：0Y最坏情况：3(n-1)比较次数：)(21)(211nninniq空间复杂度：S(n)=O(1)T(n)=O(n)湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲二、堆排序二、堆排序堆排序的特点是，堆排序的特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。堆的定义：堆的定义：堆是满足下列性质的数列r1, r2, ，rn：122iriririr 或 122iiiirrrrrir2iR2i+1湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲若将此数列看成是一棵完全二叉树，则若将此数列看成是一棵完全二叉树，则堆堆或是空树或是满足下列特性的完全二叉树：其或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左左、右子树分别是堆，并且当左/ /右子树不空右子树不空时，根结点的值小于时，根结点的值小于( (或大于或大于) )左左/ /右子树根结右子树根结点的值点的值。rir2iR2i+1湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中（完全二叉树的根）必为序列中n n个元素个元素的最大值或最小值的最大值或最小值, ,分别称作大顶堆或小分别称作大顶堆或小顶堆。顶堆。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 先建一个先建一个“大顶堆大顶堆”，即先选得一个关键字，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前，之后继续对序列中前n-1n-1记录进行记录进行“筛选筛选”，重，重新将它调整为一个新将它调整为一个“大顶堆大顶堆”，再将堆顶记录和，再将堆顶记录和第第n-1n-1个记录交换，如此反复直至排序结束。个记录交换，如此反复直至排序结束。堆排序即是利用堆的特性对记录序列进行排堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：序的一种排序方法。具体作法是：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例如：例如：40，55，49，73，12，27，98，81，64，3698，81，49，73，36，27，40，55，64，1212，81，49，73，36，27，40，55，64，9881，73，49，64，36，27，40，55，12，98建大顶堆建大顶堆交换交换98和和12筛选筛选湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲所谓“筛选筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整调整”根结点根结点使整个二叉树为堆。 方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中大（小）者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲（40，55，49，73，12，27，98，81，64，36，）40495598271273813664404955982736738112644049559827368173126440985549273681731264湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲（40，55，49，73，12，27，98，81，64，36）4098814927367355126498498140273673551264（98，81，49，73，36，27，40，55，64，12）湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲4965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 65湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲7665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void HeapAdjust(HeapType &H,int s,int m) / 算法10.10 / 已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义， /本函数调整H.rs的关键字,使H.rs.m成为一个大顶堆 /(对其中记录的关键字而言) RedType rc; int j; rc=H.rs; for(j=2*s;j=m;j*=2) / 沿key较大的孩子结点向下筛选 if(j0;-i) / 把H.r1.H.length建成大顶堆 HeapAdjust(H,i,H.length); for(i=H.length;i1;-i) / 将堆顶记录和当前未经排序子序列H.r1.i中 / 最后一个记录相互交换 t=H.r1; H.r1=H.ri; H.ri=t; HeapAdjust(H,1,i-1); / 将H.r1.i-1重新调整为大顶堆 算法描述算法描述湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度：最坏情况下T(n)=O(nlogn)q空间复杂度：S(n)=O(1)湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 归并排序的基本思想是：归并排序的基本思想是：将两个或两个以上的有序子序列将两个或两个以上的有序子序列“归并归并”为一个有序序列。为一个有序序列。10.5 归并排序归并排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲在内部排序中，通常采用的是在内部排序中，通常采用的是2-2-路归并路归并排序。即：将两个位置相邻的有序子序列排序。即：将两个位置相邻的有序子序列 有序子序列有序子序列R1.m有序子序列有序子序列Rm+1.n有有 序序 序序 列列 R1.n归并为一个有序序列。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void Merge (Elem SR, Elem TR, int i, int m, int n) / 将有序的SRi.m和SRm+1.n归并为 / 有序的TRi.n for (j=m+1, k=i; i=m & j=n; +k) / 将SR中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 将剩余的SRi.m复制到TR if (j=n) TRk.n = SRj.n; / 将剩余的SRj.n复制到TR / Merge“归并归并”算法描述如下算法描述如下： 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 97湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度：T(n)=O(nlog2n)q空间复杂度：S(n)=O(n)Ch8_9.c湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲归并排序的算法可以有两种形式：归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的递归的和递推的，它是由两种不同的程序设计思想得出的程序设计思想得出的 递归形式的归并排序是一种自顶向递归形式的归并排序是一种自顶向下的分析方法下的分析方法 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲如果记录无序序列如果记录无序序列Rs.t的两部分的两部分Rs. (s+t)/2 和和R (s+t)/2+1.t 分别按关分别按关键字有序，则利用上述归并算法很容易键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序将它们归并成整个记录序列是一个有序序列序列，由此，应该先分别对这两部分进由此，应该先分别对这两部分进行行2-2-路归并排序。路归并排序。归并排序的算法归并排序的算法湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始关键字： 49 38 65 97 76 13 2738 49 65 97 13 76 2738 49 65 97 13 27 7613 27 38 49 65 76 9749 38 65 97 76 13 27 49 38 65 97 76 13 27 湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void Msort ( Elem SR, Elem TR1, int s, int t ) / 将SRs.t进行2-路归并排序为TR1s.t。 if (s=t) TR1s = SRs; else m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort (SR, TR2, m+1, t); /递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.t / MSort算法描述算法描述湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲void MergeSort (Elem R) / 对记录序列R1.n作2-路归并排序。 MSort(R, R, 1, n); / MergeSort湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度：T(n)=O(nlogn)q空间复杂度：S(n)=O(n)Ch8_9.c湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲q多关键字排序n定义：例 对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（ ） 面值（23A）并且“花色”地位高于“面值”n多关键字排序方法q最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至将每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列10.6 基数排序基数排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲q最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列qMSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序q链式基数排序n基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法n链式基数排序：用链表作存储结构的基数排序湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n链式基数排序步骤q设置10个队列，fi和ei分别为第i个队列的头指针和尾指针q第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同q第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表q重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲例初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲n算法评价q时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 q空间复杂度：S(n)=2rd个队列指针+n个指针域空间湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲初始状态：127810906393058918450526900808302345678910f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=011223344566778910493006308318450527800810958926903106719258湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=0134477 910493006308318450527800810958926903106719258一趟收集：31016258750500810993006326927808318458909243811065二趟收集：湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲750500810993006326927808318458909243811065二趟收集：f0=0 e0=0f1=0 e1=0f2=0 e2=0f3=0 e3=0f4=0 e4=0f5=0 e5=0f6=0 e6=0f7=0 e7=0f8=0 e8=0f9=0 e9=04479287928900806308310918426927850558993003102681754三趟收集：311065湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲10.5各种排序方法的综合比较各种排序方法的综合比较 一、时间性能一、时间性能按平均的时间性能平均的时间性能来分，有三类有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好； 时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 指的是排序过程中所需的辅助空间大小。1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2. 快速排序为O(logn)，为栈所需的辅助空间;3. 归并排序所需辅助空间最多，其空间复杂度为O(n);链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。二、空间性能二、空间性能湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 对于不稳定的排序方法，只要能举出一个实例说明即可。三、排序方法的稳定性能三、排序方法的稳定性能 快速排序和堆排序是不稳定的排序方法快速排序和堆排序是不稳定的排序方法。湖北师范学院物理系湖北师范学院物理系王秀章主讲王秀章主讲作业：P60：10.1、 10.2、 10.3、10.11、 10.25、10.30、 10.43