搜索
1第10章内部排序10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较讨论210.1概述排序——是将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。排序的一个确切定义：假设含n个记录的序列为{R1,R2,R3,…,Rn}其相应的关键字序列为{K1,K2,…,Kn}需确定1,2,…,n的一种排列P1,P2,P3,…,Pn,使其相应的关键字满足如下的递增(或递减)关系:Kp1≦Kp2≦…≦Kpn即使序列{R1,R2,R3,…,Rn}成为一个按关键字有序的序列:{Rp1,Rp2,Rp3,…,Rpn}这种操作称为排序.3稳定排序方法——假设Ki=Kj(1=i,j=n,ij),且在排序前的序列中Ri领先于Rj，若在排序后的序列中Ri仍领先Rj，则称所用的排序方法是稳定的。不稳定排序方法——假设Ki=Kj(1=i,j=n,ij),且在排序前的序列中Ri领先于Rj，若在排序后的序列中Rj领先Ri，则称所用的排序方法是不稳定的。例：姓名年龄体重1李由57622王天54763七明24754张强24725陈华2453按某种稳定方法对年龄关键字进行排序姓名年龄体重3七明24754张强24725陈华24532王天54761李由57624姓名年龄体重1李由57622王天54763七明24754张强24725陈华2453按某种不稳定方法对年龄关键字进行排序姓名年龄体重4张强24723七明24755陈华24532王天54761李由5762待排序记录存放在计算机随机存储器中进行的排序过程；内部排序——待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程；外部排序——5按排序过程中依据的不同原则对内排方法分类：（1）插入排序（2）交换排序（3）选择排序（4）归并排序（5）基数排序按内排过程中所需的工作量分类：（1）简单的排序方法，其时间复杂度为O(n×n)（2）先进的排序方法，其时间复杂度为O(nlogn);（3）基数排序，其时间复杂度为O(d×n)排序算法的两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移至另一个位置；6待排序的记录序列可有三种存储方式：（1）待排序的记录存放在地址连续的一组存储单元上。（2）待排序的记录存放在静态链表中。（3）待排序的记录本身存储在一组地址连续的存储单元内,同时另设一个指示各个记录存储位置的地址向量。待排序记录的数据类型设为：P264710.2插入排序插入排序直接插入排序折半插入排序2-路插入排序表插入排序希尔排序10.2.1直接插入排序直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)用L(sqlistL)的L.r[1].key..L.r[8].key依次存储L.r[1].key..L.r[8].key是递增有序的直接插入排序8直接插入排序的过程:[初始关键字]r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]4938659776132749`第一趟插入3849659776132749`第二趟插入3849659776132749`第三趟插入3849659776132749`第四趟插入3849657697132749`第五趟插入1338496576972749`第六趟插入1327384965769749`第七趟插入1327384949`657697i=2i=3i=4i=5i=6i=7i=89直接插入排序算法分析:有n个记录待排序,需进行2..n共n-1趟插入;一级算法：Voidinsertsort(sqlist&L){for(i=2;i=L.length;++i)第i趟插入；}第i趟插入完成的功能:在含有i-1个记录的有序序列r[1..i-1]中插入一个记录r[i],插入后变成含有i个记录的有序序列r[1..i]。10第i趟插入的算法二级算法：例：第i=7趟插入：if(LT(L.r[i].key,L.r[i-1].key)){L.r[i]插入到L.r[1]..L.r[i-1]中}L.r[0]=L.r[i];L.r[i]=L.r[i-1];For(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];1338496576972749`1234567811三级算法：Voidinsertsort(sqlist&L){for(i=2;i=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];For(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}12直接插入排序的性能分析:(1)空间:只需一个记录的辅助空间r[0].(2)时间:基本运算:比较和移动记录;比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序:关键字比较次数:n-1移动记录的次数:0(2)待排序序列关键字逆序排序:关键字比较次数:2+3+…+n=(n+2)(n-1)/2移动记录的次数:3+4+5+…+(n+1)=(n+4)(n-1)/2(3)待排序序列关键字随机排序:关键字比较次数:(n-1)(n+4)/4移动记录的次数:(n+4)(n-1)/4直接插入排序算法的时间复杂度为O(n×n)1310.2.2其它插入排序折半插入排序:把直接插入算法中对插入位置的搜索从顺序搜索改进为折半搜索.VoidBinsertsort(sqlist&L){for(i=2;i=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];For(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}P267算法10.214折半插入排序的性能分析:(1)空间:只需一个记录的辅助空间r[0];(2)时间:基本运算:比较和移动记录;折半插入排序算法的时间复杂度为O(n×n)152-路插入排序为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)另设一个和r同类型的数组d,首先将r[1]赋值给d[1],并将d[1]看成是在排好序的序列中处于中间位置的记录,然后从r中第2个记录起依次插入到d[1]之前或之后的有序序列中.先将待插记录的关键字和d[1]的关键字进行比较.若r[i].keyd[1].key,则将r[i]插入到d[1]之前的有序表中,反之,则将r[i]插入到d[1]之后的有序表中.算法实现的关键设计:将d看成是一个循环数组,并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置.16d[1]d[2]d[3]d[4]d[5]d[6]d[7]d[8][初始关键字]4938659776132749`i=1:49first↑↑finali=2:4938first↑↑finali=3:493865↑finalfirst↑i=4:49386597↑finalfirst↑i=5:4938657697↑finalfirst↑i=6:493865769713↑finalfirst↑i=7:49386576971327↑finalfirst↑i=8:4949`657697132738↑final↑first172-路插入排序的性能分析:(1)空间:(2)时间:基本运算:比较和移动记录;2-路插入排序算法的时间复杂度为O(n×n)1810.2.3希尔排序从直接插入排序待排序序列基本有序可提高效率待排序序列的记录数n很小时可提高效率希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序.例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)19[初始关键字]r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]4938659776132749`第一趟排序后:(d1=3)2738134949`659776第二趟排序后:(d2=2)132749`97第三趟排序后:(d3=1)1327384949`6576973849657620希尔排序算法的实现:Voidshellsort(sqlist&L,intdlta[],intt){for(i=0;it;++i)以dlta[i]为增量的一趟排序；}Shellinsert（sqlist&L,dlta[i]);Voidinsertsort(sqlist&L){for(i=2;i=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];L.r[i]=L.r[i-1];For(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}(1)记录的增量为dk;(2)r[0]不是哨兵。j=0，插入位置已找到。P272算法10.421希尔排序的性能分析：(1)空间:只需一个记录的辅助空间r[0];(2)时间:基本运算:比较和移动记录;时间复杂度为：O（n3/2）增量的取法应注意：使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须为1。2210.3快速排序起泡排序的基本思想:首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。然后进行第二趟起泡排序，对前n-1个记录进行同样操作。……结束的条件:(1)趟数为n-1;(2)直到在某趟排序过程中没有进行过交换记录的操作为止。23例:有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49`)第一趟:4938659776132749`3849659776132749`3849659776132749`3849659776132749`3849657697132749`3849657613972749`3849657613279749`38496576132749`97第一趟进行7次比较244938659776132749`38496576132749`97初始关键字第一趟排序后384965132749`76第二趟排序后3849132749`65第三趟排序后3813274949`第四趟排序后13273849第五趟排序后132738第六趟排序后1327第七趟排序后整个排序过程25起泡排序算法的性能分析:(1)空间:只需一个记录的辅助空间.(2)时间:基本运算:比较和移动记录;比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序:关键字比较次数:n-1移动记录的次数:0(2)待排序序列关键字逆序排序:关键字比较次数:(n-1)+(n-2)+…+1=n(n-1)/2移动记录的次数:3n(n-1)/2(3)待排序序列关键字随机排序:关键字比较次数:(n-1)(n+2)/4移动记录的次数:3n(n-1)/4起泡排序算法的时间复杂度为O(n×n)26快速排序的基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。算法实现分析：（