《第十章内排序》-课件.ppt

 10.1 基本概念? 介绍： (1) 排序的数据； (2) 稳定性； (3)评价算法 进行排序的数据一般总是一个”文件”中的各记录的关键字段。选择关键字段要求选择其值几乎都不相同的字段。如果出现有相同的关键字段值时，排序时就提出一个稳定性问题： 稳定性---对于具有相同关键字值的记录，排序后仍保持原来的相对位置(前后)。称为排序是”稳定的”，否则是”不稳定的”。 对于排序，是经常进行的工作，所以排序算法好坏对整个运行有一定的影响。怎样评价算法好坏呢? 主要有两条： (1) 运行时间。主要看数据比较或移动次数 (2) 附加空间。 运行的时间都是估计，根据平均或最坏情况，所以有时也要看数据分布情况；作特殊的评价。 10. 2 扦入排序? 指导思想：是将要排序的记录，按其关键字值大小扦入到前面已排序的记录中的适当位置。 扦入排序分四种方法：  （1） 直接扦入；  （2） 其它扦入；  （3）表扦入 （4） Shell(希尔)排序 一、直接扦入排序 存储结构说明如下： ... typedef struct {  ... keytype key; /* 顺序码说明 */  } elemtype; /* 元素类型说明 */ elemtype x[MAXNUM]; /* 排序序列说明 */ 1．? 直接插入排序 (1) 方法：从第二个记录开始，在它前面找保持排序的合适位置，将此记录扦入。再把第三个以同样方法扦入，直到所有都排序完。 在扦入第i个记录时，前面的i-1个记录一定是已排序好的。 例：待排序的记录共７个 5， 3， 4， 9， 7， 1， 4 第1次： R[0]=3 5 3 4 9 7 1 4 第2次： R[0]=4 3 5 4 9 7 1 4 第3次： R[0]=9 3 4 5 9 7 1 4  第4次： R[0]=7 3 4 5 9 7 1 4 第5次： R[0]=1 3 4 5 7 9 1 4 第6次： R[0]=4 1 3 4 5 7 9 4  1 3 4 4 5 7 9 (2) 算法： void InsertSort(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]; for(j=i-1; LT(L.r[0].key, L.r[j].key);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } }(3) 比较和移动次数分析 空间：一个附加空间； 时间：O（n2）。 二、其它扦入排序 1.折半插入排序 （1）方法：与直接扦入排序方法基本一致，就是在查找排序位置时，使用折半查找的比较方法。 折半查找的比较方法：(在讲查找时已讲)由于在扦入Ki时，前i-1个记录(K1，K2，…，Ki-1)是已经排序好的。找扦入位置时，总是比较┗i/2┛(取i/2的下限值)位置的值，如果： ┗i/2┛位置值： 在后一半进行二分法比较 Ki ┗i/2┛位置值： 在前一半进行二分法比较 =┗i/2┛位置值： 在该值后面扦入（保持稳定性） 直到找到一个合适的位置。 （2）算法