数据结构内部排序.ppt
数据结构 第10章 内部排序学习目的与要求：学习目的与要求：1.深刻理解排序的定义和各种排序方法的特点深刻理解排序的定义和各种排序方法的特点, 并能加以灵活应用并能加以灵活应用;2.熟练掌握各种排序方法的执行过程；熟练掌握各种排序方法的执行过程；3.熟练掌握各种排序方法的时间复杂度的分析方法，从熟练掌握各种排序方法的时间复杂度的分析方法，从“关键字间关键字间的比较次数和记录的移动次数的比较次数和记录的移动次数”分析排序算法的平均情况和最坏分析排序算法的平均情况和最坏情况的时间性能情况的时间性能;4.4.理解排序方法理解排序方法“稳定稳定”或或“不稳定不稳定”的含义。的含义。数据结构 第10章 内部排序概述概述插入排序插入排序交换排序交换排序选择排序选择排序基数排序基数排序归并排序归并排序各种排序方法的比较各种排序方法的比较数据结构 第10章 内部排序概述概述1 1基本概念基本概念排序排序：将数据元素：将数据元素( (或记录或记录) )的一个任意序列的一个任意序列, ,重新排列重新排列成一个按关键字有序的序列。成一个按关键字有序的序列。排序方法的稳定性排序方法的稳定性：对关键字相同的数据元素，排：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是序前后它们的领先关系保持不变，则称该排序方法是稳定的稳定的；反之，称该排序方法是；反之，称该排序方法是不稳定的不稳定的。内部排序内部排序：待排序记录存放在计算机的内存中进行：待排序记录存放在计算机的内存中进行的排序。的排序。数据结构 第10章 内部排序外部排序外部排序：待排序记录的数量很大，以致内存一次：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。的排序。排序的时间开销排序的时间开销：排序的时间开销是衡量算法好坏的排序的时间开销是衡量算法好坏的最重要的标志。最重要的标志。排序的时间开销可用算法执行中的排序的时间开销可用算法执行中的数据数据比较次数比较次数与与数据移动次数数据移动次数来衡量。算法运行时间代价的来衡量。算法运行时间代价的估算一般都估算一般都按平均情况按平均情况进行估算。对于那些进行估算。对于那些受记录关键受记录关键字序列初始排列及记录个数影响较大的字序列初始排列及记录个数影响较大的，需要需要按最好情按最好情况况和和最坏情况最坏情况进行估算进行估算。数据结构 第10章 内部排序2 2排序的分类排序的分类按排序过程依据的不同原则进行分类：按排序过程依据的不同原则进行分类：交换排序交换排序选择排序选择排序归并排序归并排序计数排序计数排序插入排序插入排序按工作量进行分类：按工作量进行分类：先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlog2n)简单的排序方法简单的排序方法,其时间复杂度为其时间复杂度为O(n2)基数排序基数排序基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)数据结构 第10章 内部排序3 3排序的基本操作和记录的存储方式排序的基本操作和记录的存储方式排序过程中需要的两种基本操作：排序过程中需要的两种基本操作：（1）比较关键字的大小；）比较关键字的大小；（2）将记录从一个位置移至另一个位置。）将记录从一个位置移至另一个位置。待排序记录序列可有下列三种存储方式：待排序记录序列可有下列三种存储方式：（1）记录存放在）记录存放在一组连续的存储单元一组连续的存储单元中；类似于线性表的顺序中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在）记录存放在静态链表静态链表中；记录次序由指针指示，实现排序中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。不需移动记录，仅需修改指针。链排序链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的个记录存储位置的地址向量地址向量，排序过程中不移动记录本身，而，排序过程中不移动记录本身，而移动地址向量中相应记录的移动地址向量中相应记录的地址地址。排序结束后再根据地址调整。排序结束后再根据地址调整记录的存储位置。记录的存储位置。地址排序地址排序数据结构 第10章 内部排序4 4待排序记录的数据类型待排序记录的数据类型#define MAXSIZE 20typedef struct int key; InfoType otherinfo;RedType;typedef struct RedType rMAXSIZE+1; /0单元作为哨兵单元作为哨兵 int length;SqList;数据结构 第10章 内部排序概述概述插入排序插入排序交换排序交换排序选择排序选择排序基数排序基数排序归并排序归并排序各种排序方法的比较各种排序方法的比较数据结构 第10章 内部排序插入排序插入排序直接插入排序直接插入排序 插入排序的基本思想是：每步将一个待排序的记插入排序的基本思想是：每步将一个待排序的记录，按其关键字大小，录，按其关键字大小，插入插入到前面已经到前面已经排好序排好序的一组的一组记录的记录的适当位置适当位置上，直到记录上，直到记录全部插入全部插入为止。为止。折半插入排序折半插入排序2-路插入排序路插入排序表插入排序表插入排序希尔排序希尔排序插入排序插入排序数据结构 第10章 内部排序1直接插入排序直接插入排序基本思想：基本思想： 当插入第当插入第i (i 1) 个记录时，前面的个记录时，前面的r1, r2， ， ri-1已经排好序。这时，用已经排好序。这时，用ri的关的关键字与键字与ri-1， ri-2， 的关键字顺序进行比的关键字顺序进行比较，找到插入位置即将较，找到插入位置即将ri插入，原来位置上之插入，原来位置上之后的所有记录依次向后顺移。后的所有记录依次向后顺移。数据结构 第10章 内部排序例例49 38 65 97 76 13 27（ ）i=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=7 (13 38 49 65 76 97 ) 27j9727j76j65j49j38j排序结果：排序结果： (13 27 38 49 65 76 97)数据结构 第10章 内部排序直接插入排序的算法直接插入排序的算法void InsertSort(SqList &L) /对待排序序列对待排序序列L进行直接插入排序进行直接插入排序 for(i=2; i=L.length; +i) if (L.ri.keyL.ri-1.key ) L.r0 = L.ri; / 复制为哨兵复制为哨兵 L.ri=L.ri-1; for(j = i-2; L.r0.key L.rj.key; -j) L.rj+1 = L.rj; / 记录后移记录后移 L.rj+1 = L.r0; /记录插入记录插入 / InsertSort数据结构 第10章 内部排序算法评价算法评价记录的比记录的比较次数较次数记录的移记录的移动次数动次数最好情况最好情况最坏情况最坏情况ni=21n10ni 2(n1)(n2)i2ni 2(n1)(n4)(i+1)2时间复杂度：时间复杂度：T(n)=O(n)结论：结论：空间复杂度：空间复杂度： S(n)=O(1)直接插入排序是一个直接插入排序是一个稳定稳定的排序方法。的排序方法。数据结构 第10章 内部排序2折半插入排序折半插入排序基本思想基本思想： 利用直接插入排序的思想，只是在排序过程中，为利用直接插入排序的思想，只是在排序过程中，为减少查找次数，对已排好序的序列减少查找次数，对已排好序的序列 r1, r1, , ri-1 ，利用折半查找法寻找利用折半查找法寻找 ri 的插入位置。的插入位置。例例 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20.i=7 6 (6 13 30 39 42 70 85 ) 20数据结构 第10章 内部排序i=8 20 (6 13 30 39 42 70 85 ) 20lhmi=8 20 (6 13 30 39 42 70 85 ) 20lhmi=8 20 (6 13 30 39 42 70 85 ) 20l, m, hi=8 20 (6 13 30 39 42 70 85 ) 20lhi=8 20 (6 13 20 30 39 42 70 85 )数据结构 第10章 内部排序算法描述如下：算法描述如下：void Bin_InsertSort(SqList &L) /对待排序序列对待排序序列L进行折半插入排序进行折半插入排序 for(i=2; i=L.length; +i) low = 1; high = i-1; while(low=high) mid = (low+high)/2; if(r.mid.key high; j- ) L.rj+1 = L.rj; / 记录后移记录后移 L.rhigh+1 = L.r0; /记录插入记录插入 / Bin_InsertSort数据结构 第10章 内部排序算法分析算法分析折半插入排序减少了关键字间的比较次数（由折半插入排序减少了关键字间的比较次数（由O(n)O(n)下降到下降到O(nlogO(nlog2 2n)n)。折半插入排序的记录移动次数仍为折半插入排序的记录移动次数仍为O(n) 。折半插入排序的时间复杂度仍为折半插入排序的时间复杂度仍为O(n) ，空间复杂，空间复杂度仍为度仍为O() 。折半插入排序是一个折半插入排序是一个稳定稳定的排序方法。的排序方法。数据结构 第10章 内部排序32-路插入排序路插入排序基本思想基本思想：利用直接插入排序的思想，只是在排序过程：利用直接插入排序的思想，只是在排序过程中，为减少记录的比较和移动次数，但需要中，为减少记录的比较和移动次数，但需要n个记录的个记录的辅助空间。其做法是：另设一个和辅助空间。其做法是：另设一个和L.r同类型的数组同类型的数组D，首先将首先将L.r1赋给赋给D.r1，并将，并将D.r1看成是在排好序的看成是在排好序的序列中处于中间位置的记录，然后从序列中处于中间位置的记录，然后从L.r中第二个记录中第二个记录起依次到起依次到D.r1之前或之后的有序序列中。之前或之后的有序序列中。例例 30 13 70 85 39 42 6 20排序过程中排序过程中D的状态变化如下：的状态变化如下：i=1 (30) firstfinali=2 (30) 13 firstfinal数据结构 第10章 内部排序 30 13 70 85 39 42 6 20i=3 (30) 70 13 firstfinali=4 (30) 70 85 13 firstfinali=5 (30) 39 70 85 13 firstfinali=6 (30) 39 42 70 85 13 firstfinali=7 (30) 39 42 70 85 6 13 firstfinali=8 (30) 39 42 70 85 6 13 20firstfinal数据结构 第10章 内部排序算法描述如下：算法描述如下：void Two_InsertSort(SqList L，SqList &D ) /对待排序序列对待排序序列L进行进行2-路插入排序路插入排序 D.r1 = L.r1; D.length = L.length; first = final = 1; for( i =2; i= L.length; i+ ) x = L.ri.key; if ( x D.r1.key ) if ( first = 1 ) D.rD.length =
