数结结构-排序1(动态演示效果).ppt

《数结结构-排序1(动态演示效果).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序排序§10.1排序概述§10.2插入排序§10.3交换排序§10.4选择排序§10.5归并排序§10.6基数排序§10.1排序概述操作对象：同类型数据元素的集合。操作目标：将无序的数据元素序列排列成按关键字值有序的序列。排序排序概述稳定排序与非稳定排序：设：Ri.key==Rj.key排序前Ri领先于Rj；经排序后若Ri仍然领先于Rj，则是稳定排序算法；若不能保证这一点则是非稳定排序算法。排序排序概述内部排序与外部排序：内部排序----待排序的记录全部存放在内存;外部排序----一部分放在内存，一部分在外存。排序过程中存在着内、外存的数据交换。排序排序概述排序的基本动作：①

2、比较②移动排序性能的评价：对比较次数和移动次数的评估排序排序概述排序方法：插入排序直接插入排序、折半插入排序、2路插入排序表插入排序、希尔排序交换排序冒泡排序、快速排序选择排序简单选择排序、堆排序、树形选择排序归并排序2路归并排序基数排序排序排序概述排序§10.1排序概述§10.2插入排序§10.3交换排序§10.4选择排序§10.5归并排序§10.6基数排序§10.2插入排序10.2.1直接插入排序10.2.2折半插入排序10.2.3二路插入排序10.2.4表插入排序10.2.5希尔排序排序插入排序直接插入排序算法思想：排序区间R[1..n]；在排序的过程中，整个排序区间被分为两个子

3、区间：有序区R[1..i-1]和无序区R[i..n]；共进行n－1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1nRR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n插入排序直接插入排序初态：有序区为R[1]58154645900832R12345670监视哨1558R464590083212345670第一趟，i＝2；15<58，15赋给监视哨；有序区中所有大于15的记录右移一位将15放入腾出的空位i=258154645900832R12345670初态：4658154645900

4、832R12345670R4590083212345670第二趟，i＝3；46<58，46赋给监视哨；有序区中所有大于46的记录右移一位将46放入腾出的空位i=3155815584645900832R12345670初态：第一趟后：R90083212345670第三趟，i＝4；45<58，45赋给监视哨；有序区中所有大于45的记录右移一位将45放入腾出的空位i=41545584658154645900832R1234567015584645900832R1234567015465845900832R12345670初态：第一趟后：第二趟后：第四趟，i＝5；90>58，没有移动发生；i=558

5、154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567090154546580832R12345670初态：第一趟后：第二趟后：第三趟后：第五趟，i＝6；i=6R321234567008154546589058154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567015454658900832R12345670初态：第一趟后：第二趟后：第三趟后：第

6、四趟后：第六趟，i＝7；i=7R1234567008153245465858154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567015454658900832R1234567008154546589032R1234567090初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟后：存储结构----以顺序存储结构为例#defineMAXSIZE200typedefstruct{//结点类型KeyTypekey;InfoTypeotherinfo;}RecordType;

7、typedefstruct{//排序表类型RecordTypeR[MAXSIZE+1];intlength;}SqList;keyotherinfoR[]length插入排序直接插入排序直接插入排序算法：voidInsertSort(SqList&L){//对顺序表L作直接插入排序for(i=2;i<=L.length;i++)if(L.R[i].key