数据结构与算法 教学课件 作者 王曙燕 chapter9 排序.ppt

《数据结构与算法 教学课件 作者 王曙燕 chapter9 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、19.1概述9.2插入类排序9.4选择类排序9.3交换类排序9.5归并排序9.6分配类排序9.7外部排序9.8算法总结2排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,979.1概述3排序的定义：假设含n个记录的序列为{a0,a1,…，an-1}其相应的关键字序列为{K0,K1,…，Kn-1}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp0≤Kp1≤…≤Kpn-1按此固有关系

2、将上式记录序列重新排列为{ap0,ap1,…，apn-1}的操作称作排序。9.1概述4排序内部排序外部排序整个排序过程不需要访问外存便能完成。若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成。稳定排序不稳定排序排序相同关键字的领先关系在排序过程中未发生变化。相同关键字的领先关系在排序过程中发生变化。9.1概述5内部排序的过程：是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区内部排序的方法9.1概述6基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类其它方法9.1概述7待排记录

3、的数据类型定义如下:#defineMAXSIZE1000typedefintKeyType;typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;typedefstruct{RcdTyper[MAXSIZE+1];intlength;}SqList;9.1概述89.2插入类排序将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。有序序列a[1..i-1]a[i]无序序列a[i..n-1]一趟直接插入排序的基本思想：有序序列a[1..i]无序序列a[i+1..n-1]99.2插入类排序实现

4、“一趟插入排序”可分三步进行：3．将a[i]插入(复制)到a[j+1]的位置上。2．将a[j+1..i]中的所有记录均后移一个位置；1．在a[1..i-1]中查找a[i]的插入位置，a[1..j].keya[i].key

5、35486237777455556277514143548556277635354855627779898从r[i-1]起向前进行顺序查找，监视哨设置在r[0]；r[0]=r[i];循环结束表明r[i]的插入位置为j+1r[0]jr[i]for(j=i-1;r[0].key

6、①直接插入排序13令i=2，3，…,n,实现整个序列的排序。for(i=2;i<=n;++i)if(r[i].key

7、.r[0];时间复杂度：O(n2)159.2插入类排序②折半插入排序因为r[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在r[1..i-1]中查找r[i]的插入位置”，如此实现的插入排序为折半插入排序。14364952586180239775ilowhighmhighmhighmlow例如:插入位置L.r16数据结构9.2插入类排序第9章内部排序②折半插入排序voidBiInsertionSort(SqList&L){}在L.r[1..i-1]中折半查找插入位置；fo