数据结构(C语言版)第7章ppt课件.ppt

《数据结构(C语言版)第7章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章排序为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。排序的概念及种类插入法排序的各种具体实现方法及算法分析选择法排序的各种具体方法的实现及时间性能分析交换法排序的具体实现及性能分析归并排序和基数排序的各自实现算法2021/7/3017.1查找与表验证7.1.1查找与排序关系1.程序7-1顺序查找：intseqsearch(intlist[],intsearchnum,intn){inti;list[n]=searchnum;for(i=0;list[i]!=searchnum;i++);return((i

2、=(n+1)/2=O(n)2021/7/302查找效率对比：高效的排序、查找策略程序7-2折半查找:intbinserach(elementlist[],intsearchnum,intn){intlest=0,right=n-1,middle;while(left<=right){middle=(left+right)/2;switch(compare(list[middle].key,searchnum)){case-1:left=middle+1;case0:returnmiddle;case1:right=middle-1;}return-1;}O(log2n)<

3、n)2021/7/303查找效率对比：高效的排序、查找策略程序7-3顺序表验证O(m·n)voidverify1(elementlist1[],elementlist2[],intn,intm){inti,j;intmarked[MAX_SIZE];for(i=0;i

4、!marked[i])printf(“%disnotinlist1”,list2[i].key;}2021/7/304程序7-4两个表快速验证：voidverify2(elementlist1[],elementlist2[],intn,intm){inti,j;sort(list1,n);sort(list2,m);while(i

5、+;}else{printf(“%disnotinlist1”,list2[i].key);j++;}for(;i

6、簿、病历、档案室中的档案、图书馆和各种词典的目录表等。假设含有n个记录的序列为：R1，R2，…，Rn}(7-1)其相应的关键字序列为：{K1，K2，…，Kn}需确定1，2，…，n的一种排序p1，p2，…，pn，使其相应的关键字满足如下关系：Kp1≤Kp2≤…≤Kpn(7-2)即使得式7-1序列成为一个按关键字有序的序列{Rp1，Rp2，…，Rpn}(7-3)这个将原有表中任意顺序的记录变成一个按关键字有序排列的过程称为排序。2021/7/3062．排序分类内部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。外部排序：由于待排序的记录数量太多，在排

7、序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。本章先介绍内部排序的各种方法，最后再讨论外部排序。主要的内部排序方法：插入排序、快速排序、堆排序、归并排序、基数排序2021/7/3077.3插入排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将