数据结构教案（苏3）.ppt

《数据结构教案（苏3）.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章内部排序在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是所有的数据元素(记录)是按关键字有序的。需要将一个无序的数据文件转变为一个有序的数据文件。将任一文件中的记录通过某种方法整理成为按(记录)关键字有序排列的处理过程称为排序。排序是数据处理中一种最常用的操作。8.1排序的基本概念⑴排序(Sorting)排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程，其定义为：给定一组记录序列：{R1,R2,…,Rn}，其相应的关键字序列是{K1,K2,…,Kn}。确定1,2,…n的一个排列

2、p1,p2,…,pn，使其相应的关键字满足如下非递减(或非递增)关系：Kp1≤Kp2≤…≤Kpn的序列{Kp1,Kp2,…,Kpn}，这种操作称为排序。关键字Ki可以是记录Ri的主关键字，也可以是次关键字或若干数据项的组合。◆Ki是主关键字：排序后得到的结果是唯一的；◆Ki是次关键字：排序后得到的结果是不唯一的。⑵排序的稳定性若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(i≠j，i,j=1,2,…n)，且在排序前Ri先于Rj(i

3、能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。评价排序算法的标准有：执行时间和所需的辅助空间，其次是算法的稳定性。若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是O(1)，则称排序方法是就地排序，否则是非就地排序。⑶排序的分类待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。①待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序；②待排序的记录数太多：所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。⑷内部排

4、序的基本操作对内部排序地而言，其基本操作有两种：◆比较两个关键字的大小；◆存储位置的移动：从一个位置移到另一个位置。第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：①记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的；②记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；③记录存储在一组连续地址的存储空间：构造另一个辅助表来保存各个记录的存放地址(指针)：排序过程不需要移动记录，而仅需

5、修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。①比较适合记录数较少的情况；而②、③则适合记录数较少的情况。为讨论方便，假设待排序的记录是以①的情况存储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。待排序的记录类型的定义如下：#defineMAX_SIZE100typedefintKeyType;typedefstructRecType{KeyTypekey;/*关键字码*/infoTypeotherinfo;/*其他域*/}RecType;typedefRecTypeSeqList[n+1];8.2插

6、入排序采用的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前，设以前的所有记录R1,R2,….,Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。最基本的插入排序是直接插入排序(StraightInsertionSort)。8.2..1直接插入排序1.排序思想将待排序的记录Ri，插入到已排好序的记录表R1,R2,….,Ri-1中，得到一个新的、记录数增加1的有序表。直到所有的记录都插入完为止。设待排序的记录顺序存放在数组R[1…n]中，在排序的某一时刻，将记录序列分成两部分：◆R[1…i-1]：已排好序的有序部分；◆R[i…n]

7、：未排好序的无序部分。显然，在刚开始排序时，R[1]是已经排好序的。例：设有关键字序列为：7,4,-2,19,13,6，直接插入排序的过程如下图10-1所示：初始记录的关键字：[7]4-219136第一趟排序：[47]-219136第二趟排序：[-247]19136第三趟排序：[-24719]136第四趟排序：[-2471319]6第五趟排序：[-24671319]图10-1直接插入排序的过程2.算法实现voidstraight_insert_sort(SqlistR){inti,j;for(i=2;i<=n;i++){R[0]=R[i];j=

8、i-1;/*设置哨兵*/while(LT(R[0].key,R[j].key)){R[j+1]=R[j];j--;}/*查找插入位置*/R[j+1]=