数据结构 第十章课件

1、第10章内部排序，1，PPT学习通信，10.2插入排序，10.1概要，10.3快速排序，10.4选择排序，10.5合并排序，10.6基数排序，10.7各种内部排序方法的比较研究，2，PPT学习通信， 排序是计算机内频繁进行的操作，其目的是将“无序”记录序列调整为“有序”记录序列。 举例来说，可调整以下关键字序列52、49、80、36、14、58、61、23、97、75以使14、23、36、49、52、58、61、75、80、97、3、PPT学习通信，且可生成n个记录K2、Kn )、和这些关键字可以相互比较，即，它们之间存在非减少关系Kp1Kp2Kpn，将根据该关系将记录序列重新排序(Rp1、R

2、p2、以及Rpn )的操作称为排序。排序的形式化定义、4、PPT学习通信、内部排序和外部排序、要排序的记录全部存储在内存中，如果整个排序过程不需要访问外部内存，则这种排序问题称为内部排序，要排序的记录数量多， 如果无法一次将所有记录存储在内存中，则在排序过程中还需要访问外部时，这种排序问题称为外部排序。 5、PPT学习了交流、排序方法的稳定性，在一种排序方法中，排序后具有相同关键字的记录如果保持原来的相对顺序就很稳定，否则称为不稳定。 例如：成绩不升顺序排序，6、PPT学习沟通，排序方法的稳定性由方法本身决定。 对于不稳定的排序方法，与其描述形式无关，总是举出了不稳定的实例，相反，对于稳定的排

3、序方法，总是找到不稳定的描述形式。 举重比赛中的选手成绩表，在排名前体重增加有秩序，在排名后成绩没有上升。 必须采用稳定的排序方法，7、PPT学习交流、内部排序的方法，内部排序的过程是逐渐扩大记录秩序长度的过程。一次排序、排序区域、排序区域、排序区域、排序区域、8、PPT学习通信，基于不同的“放大”排序的长度的方法，内部的排序方法大致分为以下类型：插入类、交换类、选择类、合并类、其他PPT学习通信，1 .通过对插入类、无序子序列中的一个或几个记录进行“插入”，增加记录的排序子序列的长度。 10、PPT学习交流，2 .交换类，通过“交换”无序序列的记录，获得其中关键字最小或最大的记录，添加到秩序

4、子序列，增加记录秩序子序列的长度。 11、PPT学习通信，3 .选择类，从记录的无序子序列中选择关键字最小或最大的记录，添加到有序子序列中，增加记录的有序子序列的长度。 12、PPT学习通信，4 .合并类通过“合并”两个或多个记录秩序子序列，逐渐增加记录秩序序列的长度。 5 .其他方法、13、PPT学习交流、存储方式、排序操作通常可以通过以下存储结构进行：顺序表、链表(线性链表、静态链表)、索引顺序表、14、PPT学习交流、#define MAXSIZE 20 /顺序表的最大长度的假设值type /请将关键字类型设定为整数typedef struct KeyType key关键字字段InfoT

5、ype otherinfo； /其他域RcdType； /记录类型typedef struct RcdType rMAXSIZE 1； 用作/r0空闲或监视哨单元int length顺序表长度SqList； /顺序表类型、要排序记录的数据类型、15、PPT学习通信、10.2插入排序、16、PPT学习通信、顺序序列R1.i-1、Ri、顺序序列Ri.n、顺序序列R1.i、顺序序列Ri 1.n、17将Rj 1.i-1中的所有记录向后移动一个位置，R1.i-1中的Ri插入位置，R1.j.key Ri.key Rj 1.i-1.key； 18、PPT学习交流，直接插入排名(基于逐次搜索)，不同的具体实现

6、方式导致不同的算法描述，插入一半排名(基于一半搜索)，希尔排名(基于逐次缩小增量)，19、PPT L.ri=L.ri-1； for(j=i-2； LT(L.r0.key，L.rj.key) -j ) L.rj 1=L.rj； L.rj 1=L.r0； 在顺序序列r1.i-1中查找ri的插入位置时，直接利用“顺序检索”来实现。 10.2.1直接插入排名，20、PPT学习通信、voidinsertsort、算法10.1 (p265 )、21、PPT学习通信i=2(38)(38)65977627、I=3(38 ) (38 ) (386597 ) 7627，I=5(76 ) (386597 ) 132

7、7 I=6(13 ) (1338 49 65 7697 ) 2749，i=7 (27)(13 27 38 49 65 76 97)49，I=8(49)(132738496597)97 )，监视(1)“比较”序列中的两个关键字的大小、23、PPT学习通信、直接插入排序性能分析、最佳情况(文件初始状态顺序):最大比较次数：最坏情况(文件初始状态顺序):最小移动次数：最小移动次数：最大移动次数：24， 由于PPT学习通信r1.i-1是关键字顺序，所以实现为“用r1.i-1查找ri的插入位置”的插入排序是半插入排序。10.2.2折半插入排名、25、PPT学习通信、voidsbinsertsort (s

8、qlist/for/binsertsort或high 1、算法10.2 (p267 )、26、PPT学习通信low，m，high，14 36 49 52 58 61 80，23 97 75，I，low，high，m，low，例如：还有：插入位置，插入位置，L.r，L.r，任何情况下，low=h 27、PPT学习交流，10.2.3希尔排行(缩小阶段排行)，基本思想：对排行进行“宏观”调整，再进行“微观”调整。 把记录“跳跃”后“一步一步地移动”。 具体来说： 28、PPT学习交流，将记录序列分成几个子序列，并对各自的子序列进行插入排序。 的双曲正切值。 其中，d称为递增，其值在排序中从大到小依次

9、变小，直到最后的排序变为1。 例如，将n个记录分成d个子序列： R1，R1 d，R1 2d，R1 kd R2，R2 d，R2 kd Rd，R2 d，R3d，Rkd，R(k 1)d，29，PPT来学习通信的例子：(增加序列： ) 3-1 )初始关键字： 4938659761327495504，4913，一次排序结果： 132749504659776，3827，6549，9755，7604，135538，270465， 4997二次排序结果： 13 04 49 38 27 49 55 65 97 76，三次排序结果： 041327384956597，30，PPT学习交流，选择一个增量分配序列nd1d2dt=1，其中n文件的长度； di (1it )增量(正整数) t增加个数、排序回合数。 将文档按d1分组，将相互离开d1的记录分成组，在组内用直接插入法进行排序。 按d2、dt重复上述分组和排序作业。 31、PPT学习通信、voidshellinsert (sqlist/if/shell