数据结构课件PPT110章全 第十章 内部排序old.ppt

《数据结构课件PPT110章全 第十章 内部排序old.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、概述2、插入排序3、快速排序4、选择排序5、归并排序6、基数排序7、讨论目录第十章内部排序1、概述分类：内部排序：全部记录都可以同时调入内存进行的排序。外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。定义：设有记录序列：{R1、R2………..Rn}其相应的关键字序列为：{K1、K2………..Kn};若存在一种确定的关系：Kx<=Ky<=…<=Kz则将记录序列{R1、R2………..Rn}排成按该关键字有序的序列：{Rx、Ry………..Rz}的操作，称之为排序。关系是任意的，如通常经常使用的小于、大于等关系。稳定与不稳定：若记录序列中

2、的任意两个记录Rx、Ry的关键字Kx=Ky；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。(有哪些排序方法是稳定的？哪些不稳定？？）＃defineMAXSIZE20typedefintKeyType；typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE+1];//r[0]空或作哨兵intlength;}SqList;1、概述排序中的基本操作：(1)比较关键字大小(2)移动记录前一种基本操作对大多数

3、的排序方法是必须的，而后一个操作可以通过改变记录的存储方式来予以避免。排序评价标准执行时间比较次数移动次数所需附加空间算法复杂程度1、概述待排序记录的存储方式：(1)存放在地址连续的一组存储单元中，记录之间的关系由存储位置决定，排序必须移动记录；(2)存在静态链表中，记录之间的关系由指针指示，排序不用移动记录，只需修改指针；(3)待排序记录本身存储在一组地址连续的存储单元内，同时附设一个指示记录存储位置的地址向量，排序过程中不移动记录，而移动地址向量中这些记录的地址，在排序结束后，再按照地址向量中的值调整记录的存储位置。书中算法所使用的数据类型：＃d

4、efineMAXSIZE20typedefintKeyType；typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE+1];//r[0]空或作哨兵intlength;}SqList;2、插入排序基本方法：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。r[0]用作哨兵。共执行5遍操作。每遍操作：先将元素复制内容放入r[0]，再将本元素同已排序的序列，从尾开始进行比较。在已排序的序列中寻找自己的位置，进

5、行插入。或者寻找不到，则一直进行到哨兵为止。意味着本元素最小，应该放在r[1]。每一遍，排序的序列将增加一个元素。如果序列中有n个元素，那么最多进行n遍即可。（实际只需要n-1遍）2、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序01236241061234562、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序01236241061234

6、5362424i72、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序0123624106123453624i82、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序0123624106123453624i2492、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元

7、素之中。1、直接插入排序0123624106123453610i2410102、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序0123624106123453610i24112、插入排序e.g:36、24、10、6、12存放在r数组的下标为1至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序0123624106123453610i24122、插入排序e.g:36、24、10、6、12存放在r数组的下标为1

8、至5的元素之中，用直接插入法将其排序。结果仍保存在下标为1至5的元素之中。1、直接插入排序012362410