数据结构第8章 排序

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

1、第8章排序8.1排序基本概念8.2插入类排序8.3交换类排序8.4选择类排序8.5归并排序8.6基数排序8.7各类排序方法的比较8.8外部排序排序：将一组杂乱无章的数据元素(记录)按关键字升序(或降序)重新排列的过程8.1排序基本概念1.内排序与外排序:内排序：在排序期间数据对象全部存放在内存的排序；外排序：在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。2.稳定排序与不稳定排序假设Ki=Kj，且排序前序列中Ri领先于Rj；稳定排序：若在排序后的序列中Ri仍领先于Rj，则称排序

2、方法是稳定的。不稳定排序：若在排序后的序列中Rj领先于Ri，则称排序方法是不稳定的。例，序列3158869若排序后得3688915稳定的若排序后得3688915不稳定的在排序过程中，一般进行两种基本操作：(1)比较两个关键字的大小；对排序方法是必要的(2)将记录从一个位置移动到另一个位置。采用适当的存储方式予以避免对于待排序的记录序列，有三种常见的存储表示方法：向量结构链表结构记录向量与地址向量结合2010730519x52010730195201073019x75201030195720103019x10572030195710

3、203019x19571020305710192030x205710192030x305710192030向量结构：将待排序的记录存放在一组地址连续的存储单元中。20head1073020head10730p7head2010307head201030p7head102030链表结构：记录之间逻辑上的相邻性靠指针维持，不用移动记录元素，而只需要修改指针20107305191953071020记录向量与地址向量相结合将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。移动记录本身，而修改地址

4、向量中记录的“地址”，排序结束后，再按照地址向量中的值调整记录的存储位置本章内容主要讨论在向量结构上各种排序方法的实现假设待排记录的关键字为整数，从数组下标为1的位置开始存储，下标为0的位置存储监视哨或空闲不用#defineMaxsize100//设待排序记录最多为100个元素typedefintKeyType;//假设待排序记录关键字的数据类型为整型typedefstruct{KeyTypekey;OtherTypeother_data;//待排序记录中的其他数据类型}RecordType;RecordTyper[Maxsize

5、]排序方法插入类排序选择类排序交换类排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序多关键字排序分配类排序链式基数排序基数排序的顺序表结构快速排序树形选择排序表插入排序希尔排序第8章排序8.1排序基本概念8.2插入类排序8.3交换类排序8.4选择类排序8.5归并排序8.6基数排序8.7各类排序方法的比较8.8外部排序插入排序的基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上8.2.1直接插入排序基本思想：当插入第i(i1)个对象时，前面的v[0],v[1],…

6、,v[i-1]已经排好序。这时，用v[i]的关键字与v[i-1],v[i-2],…的关键码顺序进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后顺移。该算法适合于n较小的情况，时间复杂度为O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]对于有n个数据元素的待排序列，插入操作要进行n-1次8.2.1直接插入排序直接插入排

7、序voidInsSort(RecordTyper[],intlength)/*对记录数组r做直接插入排序，length为数组的长度*/{for(i=2;i

8、6第一次排序：[2753]36156936第二次排序：[273653]156936第三次排序：[15273653]6936第四次排序：[1527365369]36第五次排序：[152736365369]直接插入类排序分析各趟排序结果21254925