第8章 查找和排序算法.ppt

《第8章 查找和排序算法.ppt》由会员分享，可在线阅读，更多相关《第8章 查找和排序算法.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 算法和数据结构基础算法和数据结构基础查找和排序算法查找和排序算法哈尔滨工业大学哈尔滨工业大学8.1 线性查找算法线性查找算法众里寻他千百度众里寻他千百度nGoogle要完成的任务要完成的任务在在“世界上最大的一堆稻草世界上最大的一堆稻草”中寻找你想要的中寻找你想要的“绣花针绣花针”查找就是指在大量的信息列表中寻找一个特定的信息元素。查查找就是指在大量的信息列表中寻找一个特定的信息元素。查找和排序算法是计算机应用中最常用的、最基本的算法找和排序算法是计算机应用中最常用的、最基本的算法。n常用的查找算法常用的查找算法线性查找（线性查找（Linear Search），也称顺序查找），也称

2、顺序查找二分查找（二分查找（Binary Search），也称折半查找），也称折半查找8.1.1线性查找算法的基本原理线性查找算法的基本原理n优点是简单直观，不要求数据表有序优点是简单直观，不要求数据表有序依次依次将记录的关键字与将记录的关键字与查找关键字查找关键字（key）进行进行比较比较在最坏情况下，即查找关键字位于所有数在最坏情况下，即查找关键字位于所有数据的尾部且数据量较大时，或者已知数据据的尾部且数据量较大时，或者已知数据中不存在该值时，查找次数将等于总数据中不存在该值时，查找次数将等于总数据量的大小。在最好情况（数据在第一个位量的大小。在最好情况（数据在第一个位置）下，只需查找一次

3、。从平均情况来看，置）下，只需查找一次。从平均情况来看，需要与一半的数组元素与查找关键字进行需要与一半的数组元素与查找关键字进行比较。比较。【例例8.18.1】中共中央总书记、国家主席、中央军委主席习近平于中共中央总书记、国家主席、中央军委主席习近平于20212021年年6 6月月2323日同正在天和日同正在天和核心舱执行任务的神舟十二号航天员聂海胜、刘伯明、汤洪波亲切通话。由多颗中继卫星核心舱执行任务的神舟十二号航天员聂海胜、刘伯明、汤洪波亲切通话。由多颗中继卫星组成的我国天基测控系统成功保障了这次天地通话清晰流畅。假设中继卫星数量为组成的我国天基测控系统成功保障了这次天地通话清晰流畅。假设

4、中继卫星数量为 n n（假（假设设n n不超过不超过4040），其中每颗卫星具有各自的编号和载重量。请编程从键盘输入某颗卫星的编），其中每颗卫星具有各自的编号和载重量。请编程从键盘输入某颗卫星的编号和载重量，当输入为负值时，表示输入结束，然后从键盘任意输入一个编号，查找并输号和载重量，当输入为负值时，表示输入结束，然后从键盘任意输入一个编号，查找并输出该编号卫星的载重量。出该编号卫星的载重量。8.1.1线性查找算法的基本原理线性查找算法的基本原理8.1.2线性查找算法的程序实现线性查找算法的程序实现#include#define N 40int ReadRecord(int num,int w

5、eight);int LinSearch(int num,int key,int n);/主函数主函数int main(void)int numN,weightN,n,pos,key;n=ReadRecord(num,weight);printf(Total satellites are%dn,n);printf(Input the searching ID:);scanf(%d,&key);pos=LinSearch(num,key,n);if(pos!=-1)/若找到若找到 printf(weight=%dn,weightpos);else /若未找到若未找到 printf(Not fou

6、nd!n);return 0;int ReadRecord(int num,int weight)int i=-1;printf(Input satellites ID and weight:n);do i+;scanf(%d%d,&numi,&weighti);while(numi 0&weighti=0);return i;int LinSearch(int num,int key,int n)for(int i=0;i high)/递归结束条件递归结束条件 return-1;/没找到没找到 if(key nummid)return BinSearch(num,key,mid+1,high

7、);/在后一子表查找在后一子表查找 else if(key nummid)return BinSearch(num,key,low,mid-1);/在前一子表查找在前一子表查找 return mid;/找到，返回找到的位置下标找到，返回找到的位置下标【例例8.28.2】将例将例8.18.1程序改为用二分查找算法实现，假设卫星的数据记录是以按编程序改为用二分查找算法实现，假设卫星的数据记录是以按编号升序排列的。号升序排列的。int BinSearch(int num,int key,int low,int high)int mid;while(low nummid)low=mid+1;/在后一子

8、表查找在后一子表查找 else if(key nummid)high=mid-1;/在前一子表查找在前一子表查找 else return mid;/找到找到 return-1;/没找到没找到8.2.2二分查找算法的递归和迭代实现二分查找算法的递归和迭代实现n这个程序存在什么隐患？这个程序存在什么隐患？n防止溢出的解决方案防止溢出的解决方案修改计算中间值的方法，修改计算中间值的方法，用减法代替加法用减法代替加法mid=low+(high-low)/2;/函数功能：用二分法计算并返回方程的根函数功能：用二分法计算并返回方程的根double Iteration(double x1,double x2

9、,double eps)double x0;do x0=(x1+x2)/2;if(Fun(x0)*Fun(x1)=eps);return x1;/函数功能：计算函数功能：计算f(x)=x3-x-1的函数值的函数值double Fun(double x)return x*x*x-x-1;8.2.3二分查找的实际应用二分查找的实际应用【例例8.38.3】用二分法求下面的用二分法求下面的一元三次方程一元三次方程 在区间在区间1,31,3上误差不大于上误差不大于10-610-6的根。先从键盘输入迭的根。先从键盘输入迭代初值代初值 x0 x0和允许的误差和允许的误差 ，然后输出求得的方程根和所然后输出求

10、得的方程根和所需的迭代次数。需的迭代次数。#include#include double Iteration(double x1,double x2,double eps);double Fun(double x);int count=0;int main(void)double x0,x1,x2,eps;do printf(Input x1,x2,eps:);scanf(%lf,%lf,%lf,&x1,&x2,&eps);while(Fun(x1)*Fun(x2)0);/输入两个异号输入两个异号数数 x0=Iteration(x1,x2,eps);printf(x=%fn,x0);print

11、f(count=%dn,count);return 0;8.2.3二分查找的实际应用二分查找的实际应用【例例8.38.3】用二分法求下面的用二分法求下面的一元三次方程一元三次方程 在区间在区间1,31,3上误差不大于上误差不大于10-610-6的根。先从键盘输入迭的根。先从键盘输入迭代初值代初值 x0 x0和允许的误差和允许的误差 ，然后输出求得的方程根和所然后输出求得的方程根和所需的迭代次数。需的迭代次数。8.3 求最值算法求最值算法n计算计算最大值最大值的方法的方法先假设这组数据中的第一个数为当前的最大值先假设这组数据中的第一个数为当前的最大值其余的数依次与当前最大值进行比较其余的数依次与

12、当前最大值进行比较一旦发现后面的某个数大于当前的最大值，则用该数修改当前的最大值一旦发现后面的某个数大于当前的最大值，则用该数修改当前的最大值？84848388876184838887618483888761848388876184838887618484888888maxValuemaxValuemaxValuemaxValuemaxValue8.3 求最值算法求最值算法#include#define N 40int ReadRecord(int num,int weight);int FindMax(int a,int n);int main(void)int numN,weightN,n

13、;n=ReadRecord(num,weight);printf(Total satellites are%dn,n);printf(The largest weight is%dn,FindMax(weight,n);return 0;int ReadRecord(int num,int weight)int i=-1;printf(Input satellites ID and weight:n);do i+;scanf(%d%d,&numi,&weighti);while(numi 0&weighti=0);return i;n【例例8.48.4】修改例修改例8.18.1的编程任务，的编

14、程任务，从键盘输入某颗卫星的编号和载从键盘输入某颗卫星的编号和载重量，当输入为负值时，表示输重量，当输入为负值时，表示输入结束，然后计算并输出载重量入结束，然后计算并输出载重量最大的卫星的重量。最大的卫星的重量。/函数功能：计算并返回数组中的最大值函数功能：计算并返回数组中的最大值int FindMax(int a,int n)int max=a0;for(int i=1;i max)max=ai;return max;结束结束i=2maxValue=x1输出输出maxValuei maxValue?是是否否maxValue=xi输入输入n开始开始输入输入n个数据存入数组个数据存入数组X Xm

15、axIndex=1maxIndex=1maxIndex=3maxIndex=3maxIndex=3？84848388876184838887618483888761848388876184838887618484888888maxValuemaxValuemaxValuemaxValuemaxValuex1x2x3x4x5maxValue=x1,maxIndex=1maxValue=xi,maxIndex=i输出输出maxValue,maxIndex只记录下标位置，能否求出最大值？8.3 求最值算法求最值算法#include#define N 40int ReadRecord(int num,

16、int weight);int FindMaxIndex(int a,int n);int main(void)int numN,weightN,n;n=ReadRecord(num,weight);printf(Total satellites are%dn,n);pos=FindMaxIndex(weight,n);printf(Satellite%d has the largest weight%dn,numpos,weightpos);return 0;int ReadRecord(int num,int weight)int i=-1;printf(Input satellites

17、ID and weight:n);do i+;scanf(%d%d,&numi,&weighti);while(numi 0&weighti=0);return i;n【例例8.58.5】修改例修改例8.48.4的编程任务，的编程任务，从键盘输入某颗卫星的编号和载从键盘输入某颗卫星的编号和载重量，当输入为负值时，表示输重量，当输入为负值时，表示输入结束，然后计算并输出载重量入结束，然后计算并输出载重量最大的卫星的编号。最大的卫星的编号。/函数功能：计算并返回数组中最大值的函数功能：计算并返回数组中最大值的下标下标int FindMaxIndex(int a,int n)int maxIndex

18、=0;for(int i=1;i amaxIndex)maxIndex=i;return maxIndex;？18483888761848388876184838887618483888761848388876111333maxIndexmaxIndexmaxIndexmaxIndexmaxIndexx1x2x3x4x58.3 求最值算法求最值算法8.4 排序算法排序算法如影随行的如影随行的“顺序顺序”n常用的排序算法主要有常用的排序算法主要有冒泡法（冒泡法（Bubble Sort）交换法（交换法（Exchange Sort）选择法（选择法（Selection Sort）快速排序（快速排序（Q

19、uick Sort）归并排序（归并排序（Merge Sort）插入排序（插入排序（Insertion Sort）8.4.1 交换排序算法交换排序算法8.4.1 交换排序算法交换排序算法/函数功能：按交换法，对卫星记录数据按载重量进行升序排序函数功能：按交换法，对卫星记录数据按载重量进行升序排序void ExchangeSort(int num,int weight,int n)int temp;for(int i=0;in-1;i+)for(int j=i+1;jn;j+)if(weightj weighti)/按载重量进行升序排序按载重量进行升序排序 temp=numj;numj=numi;

20、numi=temp;temp=weightj;weightj=weighti;weighti=temp;n【例例8.6】修改例修改例8.5的编程任务，从键盘输入某颗卫星的编号和载重量，当输入的编程任务，从键盘输入某颗卫星的编号和载重量，当输入为负值时，表示输入结束，然后对各个卫星的信息按载重量进行升序排序。为负值时，表示输入结束，然后对各个卫星的信息按载重量进行升序排序。8.4.2 选择排序算法选择排序算法/函数功能：按选择法，对卫星记录数据按载重量升序排序函数功能：按选择法，对卫星记录数据按载重量升序排序void SelectionSort(int num,int weight,int n)

21、int i,j,k,temp;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(weightj weightk)k=j;if(k!=i)temp=numk;numk=numi;numi=temp;temp=weightk;weightk=weighti;weighti=temp;8.4.3 冒泡排序算法冒泡排序算法8.4.3 冒泡排序算法冒泡排序算法void BubbleSort(int num,int weight,int n)int i,j,temp;for(i=0;ii;j-)/从后往前两两比较，小的数前移从后往前两两比较，小的数前移 if(weightj w

22、eightj-1)/按载重量进行升序排序按载重量进行升序排序 temp=numj;numj=numj-1;numj-1=temp;temp=weightj;weightj=weightj-1;weightj-1=temp;8.4.3 冒泡排序算法冒泡排序算法void BubbleSort(int num,int weight,int n)int i,j,temp;for(i=0;in-1;i+)for(j=0;j weightj+1)/按载重量进行升序排序按载重量进行升序排序 temp=numj;numj=numj+1;numj+1=temp;temp=weightj;weightj=weig

23、htj+1;weightj+1=temp;8.4.3 冒泡排序算法冒泡排序算法n优点：优点：规则简单，易于理解，实现容易，比较次数已知，算法稳定规则简单，易于理解，实现容易，比较次数已知，算法稳定n缺点缺点效率低，效率低，每次只能移动相邻两个数据每次只能移动相邻两个数据，每次交换仅向，每次交换仅向最终目最终目标移动一个位置标移动一个位置8.4.3 冒泡排序算法冒泡排序算法void BubbleSort(int a,int n)int low=0,high=n-1;/初始搜索范围初始搜索范围 int temp,j;while(low high)/继续比较的条件继续比较的条件 for(j=low;j aj+1)temp=aj;aj=aj+1;aj+1=temp;high-;/high前移一位前移一位 for(j=high;jlow;j-)/反向冒泡反向冒泡,找最小找最小 if(aj aj-1)temp=aj;aj=aj-1;aj-1=temp;low+;/low后移一位后移一位 highlow本章知识树本章知识树Q&A