第9章排序--1.ppt

《第9章排序--1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章排序Sort主讲：顾为兵(1)第9章排序(Sort)目录§9.1排序概述§9.2插入排序§9.3交换排序§9.4选择排序§9.5归并排序§9.6基数排序排序§9.1排序概述操作对象：同类型数据元素的集合。操作目标：将数据元素的无序序列排列成按关键字值有序的序列。排序概述稳定排序与非稳定排序：设：Ri.key==Rj.key假设排序前Ri的位置排列在Rj之前；经排序后若Ri的位置仍然排列在Rj之前，则是稳定排序算法；若不能保证这一点则是非稳定排序算法。排序概述内部排序与外部排序：内部排序----待排序的记录全部存放在内存;外部

2、排序----一部分放在内存，一部分在外存。排序过程中存在着内、外存的数据交换。排序概述排序的基本动作：①比较②移动排序性能的评价：对比较次数和移动次数的评估排序概述排序方法：插入排序直接插入排序、折半插入排序、2路插入排序希尔排序交换排序冒泡排序、快速排序选择排序简单选择排序、堆排序、树形选择排序归并排序2路归并排序基数排序排序概述先进排序算法：时间复杂度----O(nlogn)一般排序算法时间复杂度----O(n2)排序概述第十章排序(Sort)目录§9.1排序概述§9.2插入排序§9.3交换排序§9.4选择排序§9.5归并排序

3、§9.6基数排序排序§9.2插入排序9.2.1直接插入排序9.2.2折半插入排序9.2.3二路插入排序9.2.4希尔排序插入排序直接插入排序算法思想：排序区间R[1..n]；在排序的过程中，整个排序区间被分为两个子区间：有序区R[1..i-1]和无序区R[i..n]；共进行n－1趟排序，每趟排序都是把无序区的第一条记录Ri插到有序区的合适位置上。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1nRR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n插入排序•直接插入排序在具有n个元素的有序顺序表

4、L[]中插入新元素e，使得L仍然有序：for(i=n-1;i>=0&&L[i].key>e.key;i--)L[i+1]=L[i];L[i+1]=e;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=2

5、58154645900832R12345670初态：4658154645900832R12345670R4590083212345670第二趟，i＝3；46<58，46赋给监视哨；有序区中所有大于46的记录右移一位将46放入腾出的空位i=3155815584645900832R12345670初态：第一趟后：R90083212345670第三趟，i＝4；45<58，45赋给监视哨；有序区中所有大于45的记录右移一位将45放入腾出的空位i=41545584658154645900832R1234567015584645900832R

6、1234567015465845900832R12345670初态：第一趟后：第二趟后：第四趟，i＝5；90>58，没有移动发生；i=558154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567090154546580832R12345670初态：第一趟后：第二趟后：第三趟后：第五趟，i＝6；i=6R321234567008154546589058154645900832R123456701558464590

7、0832R1234567015465845900832R1234567015454658900832R1234567015454658900832R12345670初态：第一趟后：第二趟后：第三趟后：第四趟后：第六趟，i＝7；i=7R1234567008153245465858154645900832R1234567015584645900832R1234567015465845900832R1234567015454658900832R1234567015454658900832R1234567008154546589032R1

8、234567090初态：第一趟后：第二趟后：第三趟后：第四趟后：第五趟后：存储结构----以顺序存储结构为例#defineMAXSIZE200typedefstruct{//结点类型KeyTypekey;InfoTypeotherinfo;}Rec