数据结构10分析只是课件.ppt

《数据结构10分析只是课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构10分析10.1概述排序的定义排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列例将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,9710.1概述一般情况下，假设含n个记录的序列为{R1,R2,…，Rn},其相应的关键字序列为{K1,K2,…，Kn}这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Kp1≤Kp2≤…≤Kpn,按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…，Rpn}的操作称作排

2、序。10.1概述假设对记录的次关键字进行排序，记录之中有两条记录Ri和Rj，它们的关键字Ki和Kj相等，在排序之前记录Ri在Rj之前，若排序之后记录Ri仍在Rj之前，则称排序方法是稳定的；相反，若经过某种排序之后Ri在Rj在之后，则称所用的排序方法是不稳定的内部排序和外部排序内部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序10.1概述内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程经过一趟排序有序序列区无序序

3、列区有序序列区无序序列区10.1概述基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型插入类交换类选择类归并类其它方法10.1概述待排记录的数据类型定义如下#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RcdType;//记录类型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置intlength;//顺序表长

4、度}SqList;//顺序表10.1概述插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度归并通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度10.2插入排序一趟插入排序的基本思想有序序列R[1..i-1]R[i]无序序列R[i..n]有序序列

5、R[1..i]无序序列R[i+1..n]10.2插入排序实现“一趟插入排序”可分三步进行在R[1..i-1]中查找R[i]的插入位置；R[1..j].keyR[i].key

6、查找R[i]的插入位置”从R[i-1]起向前进行顺序查找，监视哨设置在R[0]R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].key

7、i=2，3，…,n,实现整个序列的排序for(i=2;i<=n;++i)if(R[i].key

8、r[j+1]=L.r[0];//插入到正确位置}}//InsertSort10.2插入排序内部排序的时间分析实现内部排序的基本操作有两个