数据结构c语言描述第9章

《数据结构c语言描述第9章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章内部排序第9章内部排序9.1排序的基本概念　9.2插入类排序9.3交换类排序法9.4选择类排序法9.5归并排序　9.6分配类排序9.7各种排序方法的综合比较第9章内部排序9.1排序的基本概念1.排序有n个记录的序列{R，R，…，R}，其相应关键字的序列12n是{K，K，…，K}，相应的下标序列为1，2，…，n。通过排12n序，要求找出当前下标序列1，2，…，n的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。第9章内部排序2.内部排序与外

2、部排序;根据排序时数据所占用存储器的不同，可将排序分为两类:一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。第9章内部排序假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i

3、要求的。　证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明。第9章内部排序在排序过程中，一般进行两种基本操作：　　（1）比较两个关键字的大小；　（2）将记录从一个位置移动到另一个位置。　其中操作（1）对于大多数排序方法来说是必要的，而操作（2）则可以通过采用适当的存储方式予以避免。对于待排序的记录序列，有三种常见的存储表示方法:·向量结构：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。　第9章内部排序·链表结构：采用链表结构时，

4、记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针。这种排序方式被称为链表排序。　·记录向量与地址向量结合：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。这样在排序过程中不移动记录本身，而修改地址向量中记录的“地址”，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。第9章内部排序为了讨论方便，假设待排记录的关键字均为整数，均从数组中下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。　typedefintKeyType;typedefstruct{Key

5、Typekey;OtherTypeother-data;}RecordType;第9章内部排序9.2插入类排序插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。　打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。第9章内部排序9.2.1直接插入排序直接插入排序是一种最基本的插入排序方法。其基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，K

6、i-2，…,K进行比较，将所有关键字大于Ki的记录依次向后移1动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。完整的直接插入排序是从i=2开始的，也就是说，将第1个记录视为已排好序的单元素子集合，然后将第2个记录插入到单元素子集合中。i从2循环到n，即可实现完整的直接插入排序。第9章内部排序图9.1直接插入排序示例第9章内部排序假设待排序记录存放在r［1..n］之中，为了提高效率，我们附设一个监视哨r［0］，使得r［0］始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移

7、；二是防止越界，具体算法描述如下：voidInsSort(RecordTyper［］,intlength)/*对记录数组r做直接插入排序，length为数组的长度*/{for(i=2;i