实验6 查找和排序 (2)(1)

实验六、七：查找、排序算法的应用班级 10511 学号 20103051114 姓名高卫娜一、实验目的1 掌握查找的不同方法，并能用高级语言实现查找算法。

2 熟练掌握顺序表和有序表的顺序查找和二分查找方法。

3 掌握排序的不同方法，并能用高级语言实现排序算法。

4 熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。

二、实验内容1 创建给定的顺序表。

表中共包含八条学生信息，信息如下：学号姓名班级C++ 数据结构1 王立03511 85 762 张秋03511 78 883 刘丽03511 90 794 王通03511 75 865 赵阳03511 60 716 李艳03511 58 687 钱娜03511 95 898 孙胜03511 45 602 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

3 使用二分查找方法，从查找表中查找学号为7和12的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

（注意：创建静态查找表时必须按学号的从小到大排列！）4 使用直接插入排序方法，对学生信息中的姓名进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

5 使用直接选择排序方法，对学生信息中的C成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

7 编写一个主函数，将上面函数连在一起，构成一个完整程序。

8 将实验源程序调试并运行。

三、实验结果源程序代码为：#include<iostream.h>#include<string.h>#include <stdlib.h>#define MAXSIZE 10typedef char KeyType1;typedef int KeyType2;typedef struct{//学号姓名班级C++ 数据结构KeyType1 name[20];KeyType2 xuehao;KeyType1 Class[20];double score[2];} DataType;typedef struct{DataType data[MAXSIZE+1];int len;} SeqList;//顺序表的创建void create(SeqList &L){cout<<"请输入顺序表的大小:"<<endl;cin>>L.len;cout<<"请输入顺序表中八条学生信息（学号姓名班级C++ 数据结构）:"<<endl;for(int i=1;i<=L.len;i++){cin>>L.data[i].xuehao;cin>>L.data[i].name;cin>>L.data[i].Class;cin>>L.data[i].score[0];cin>>L.data[i].score[1];}}void Input(SeqList &L){for(int i=1;i<=L.len;i++){cin>>L.data[i].xuehao;cin>>L.data[i].name;cin>>L.data[i].Class;cin>>L.data[i].score[0];cin>>L.data[i].score[1];}}//顺序表的显示void print(SeqList L){cout<<"学号姓名班级C++ 数据结构"<<endl;if(L.len==0){cout<<"该表是空表！"<<endl;return;}for(int i=1;i<=L.len;i++){cout<<" "<<L.data[i].xuehao<<" "<<L.data[i].name<<" "<<L.data[i].Class<<" "<<L.data[i].score[0]<<" "<<L.data[i].score[1];cout<<endl;}}//顺序查找方法从查找表中查找姓名为赵阳和王夏的学生void S_Search(SeqList L){char na[20];cout<<"请输入要查找的同学的姓名："<<endl;cin>>na;strcpy(L.data[0].name,na); //监视哨int i=L.len;while(strcmp(L.data[i].name,na)>0||strcmp(L.data[i].name,na)<0)i--;if(i>0){cout<<"您要查找的学生的信息："<<endl; cout<<"学号姓名班级C++ 数据结构"<<endl;cout<<" "<<L.data[i].xuehao<<" "<<L.data[i].name<<" "<<L.data[i].Class<<" "<<L.data[i].score[0]<<" "<<L.data[i].score[1];cout<<endl;}if(i<=0){cout<<"对不起，没有该同学的信息！"<<endl;}}//二分查找方法从查找表中查找学号为7和12的学生//非递归void Binary_Search(SeqList &L){int kx;cout<<"请输入您要查找的学生信息的学号："<<endl;cin>>kx;int low=1,high=L.len,mid;while(low<=high){mid=(low+high)/2;if(L.data[mid].xuehao==kx){cout<<"您要查找的学生的信息："<<endl; cout<<"学号姓名班级C++ 数据结构"<<endl;cout<<" "<<L.data[mid].xuehao<<" "<<L.data[mid].name<<" "<<L.data[mid].Class<<" "<<L.data[mid].score[0]<<" "<<L.data[mid].score[1];cout<<endl;break;}else if(L.data[mid].xuehao>kx)high=mid-1;elselow=mid+1;}if(low>high){cout<<"没有该学号的学生信息！"<<endl;}}//直接插入排序方法对顺序表直接插入排序的算法对学生信息中的姓名进行排序：void InsertSort( SeqList &L ){int i, j;for( i=2; i<=L.len; i++ )if(strcmp(L.data[i].name, L.data[i-1].name)<0){L.data[0]=L.data[i]; // 复制为哨兵for(j=i-1; strcmp(L.data[0].name, L.data[j].name)<0; j-- )L.data[j+1]=L.data[j]; // 记录后移L.data[j+1]=L.data[0]; // 插入到正确位置}print(L);}//直接选择排序方法对学生信息中的C成绩进行排序void SelectSort(SeqList &L){int i, j,k;DataType temp;for( i=1; i<L.len; i++ ){k = i;for( j=i+1; j<=L.len; j++ )if( L.data[j].score[0] < L.data[k].score[0] )k = j ;if( k != i ){temp = L.data[i];L.data[i] = L.data[k];L.data[k] =temp;}}print(L);}//冒泡排序方法对学生信息中的数据结构成绩进行排序void BubbleSort(SeqList &L){int i,j,flag=1;DataType x;for(i=1;((i<L.len)&&(flag==1));i++){flag=0;for(j=1;j<L.len-i+1;j++)if(L.data[j].score[1]>L.data[j+1].score[1]){x=L.data[j];L.data[j]=L.data[j+1];L.data[j+1]=x;flag=1;}}print(L);}void main(){SeqList L;int a;cout<<endl;while(a!=0){cout<<endl;cout<<"-------------------------欢迎使用学生信息系统----------------------------\n"<<endl;cout<<endl;cout<<" 1 ：录入学生信息 2 ：按姓名查找学生信息3：按学号查找学生信息"<<endl;cout<<endl;cout<<" 4 ：按姓名排序后学生信息5 ：按c成绩排序学生信息"<<endl;cout<<endl;cout<<" 6 ：按数据结构成绩排序后学生信息7 ：显示0 ：退出"<<endl;cout<<endl;cout<<"--------------------------------------------------------------------------"<<endl;cout<<endl;cout<<"输入您的选择为：";cin>>a;switch(a){case 1:{ create(L); break; }case 2: //顺序查找方法从查找表中查找姓名为赵阳和王夏的学生{ S_Search(L); break; }case 3:{ Binary_Search(L); break; }case 4:{cout<<"对学生信息中的姓名进行排序为："<<endl;InsertSort(L);break;}case 5:{cout<<"对学生信息中的C成绩进行从低到高排序为："<<endl;SelectSort(L);break;}case 6:{cout<<"对学生信息中的数据结构成绩进行从低到高排序为："<<endl;BubbleSort(L);break;}case 7:{ print(L); break; }case 0: exit(0);default:{cout<<"您输入的序号不正确，请重新输入："<<endl;break;}}}}建立顺序表的运行结果为图1-1：图1-1录入学生信息查找的运行结果如图1-2,图1-3：图1-2按姓名查找图1-3按学号查询排序的运行结果如下图1-4,图1-5,图1-6：图1-4按姓名排序图1-5按c成绩排序图1-6按数据结构成绩排序结束结果如图1-7:图1-7推出程序四、实验总结（1）exit(0)需要头文件#include<stdlib.h>退出程序；（2）比较字符串使用头文件#<string.h>中得strcmp（）；复制字符串使用strcpy（）；（3）从表的一端开始，向另一端逐个将给定值x与关键码进行比较；使用折半查找的前提：查找表必须是有序表；在有序表中，取中间元素作为比较对象（4）直接插入排序是一种稳定的排序方法。

实验名称：查找算法性能分析实验目的：比较不同查找算法的效率，并分析其性能。

实验时间：2022年3月15日实验地点：计算机实验室实验器材：计算机、实验软件一、实验背景随着计算机技术的发展，数据量越来越大，查找算法在数据处理中的应用越来越广泛。

查找算法的效率直接影响到数据处理的速度，因此研究不同查找算法的性能具有重要意义。

本实验旨在比较几种常见的查找算法的效率，并分析其性能。

二、实验内容1. 算法介绍（1）顺序查找顺序查找是一种最简单的查找方法，其基本思想是从线性表的第一个元素开始，依次将线性表中的元素与要查找的元素进行比较，直到找到目标元素或者查找结束。

（2）二分查找二分查找是一种效率较高的查找方法，其基本思想是将待查找的序列分为两半，每次将中间位置的元素与要查找的元素进行比较，如果相等，则查找成功；如果中间位置的元素大于要查找的元素，则将查找范围缩小到左半部分；如果中间位置的元素小于要查找的元素，则将查找范围缩小到右半部分。

重复此过程，直到找到目标元素或者查找结束。

（3）散列查找散列查找是一种基于散列函数的查找方法，其基本思想是将要查找的元素通过散列函数映射到散列表中的一个位置，然后直接访问该位置，如果找到目标元素，则查找成功；如果未找到，则查找失败。

2. 实验步骤（1）生成随机数据使用实验软件生成一组随机数据，包括顺序查找和二分查找的数据。

（2）编写查找算法根据上述算法介绍，编写顺序查找、二分查找和散列查找的代码。

（3）测试算法性能分别对三种查找算法进行测试，记录查找成功和失败的情况，统计查找成功和失败的平均时间。

三、实验结果与分析1. 顺序查找（1）查找成功实验结果显示，顺序查找在查找成功的情况下，平均查找时间为0.1秒。

（2）查找失败实验结果显示，顺序查找在查找失败的情况下，平均查找时间为0.2秒。

2. 二分查找（1）查找成功实验结果显示，二分查找在查找成功的情况下，平均查找时间为0.05秒。

电子科技大学实验报告课程名称：数据结构与算法学生姓名：学号：点名序号：指导教师：实验地点：基础实验大楼实验时间： 5月20日2014-2015-2学期信息与软件工程学院实验报告（二）学生姓名学号：指导教师：实验地点：基础实验大楼实验时间：5月20日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—排序与查找三、实验学时：4四、实验原理：快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。

一躺快速排序的算法是：1）设置两个变量I、J，排序开始的时候I：=1，J：=N2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换；4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换；5）重复第3、4步，直到I=J。

二分法查找（折半查找）的基本思想：（1）确定该区间的中点位置：mid=（low+high）/2min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1;B)如果R[mid].key<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。

实验七查找、排序的应用一、实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。

2、学会比较各种排序与查找算法的优劣。

3、学会针对所给问题选用最适合的算法。

4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。

二、实验内容[问题描述]对学生的基本信息进行管理。

[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。

要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。

[测试数据]由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握哈希表的定义，哈希函数的构造方法。

2、掌握一些常用的查找方法。

1、掌握几种常用的排序方法。

2、掌握直接排序方法。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

五、算法设计a、折半查找设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。

初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较，若key==r[mid].key，查找成功若key<r[mid].key，则high=mid-1若key>r[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败b、顺序查找从表的一端开始逐个进行记录的关键字和给定值的比较。

在这里从表尾开始并把下标为0的作为哨兵。

void chaxun(SqList &ST) //查询信息{ cout<<"\n************************"<<endl;cout<<"~ (1)根据学号查询 ~"<<endl;cout<<"~ (2)根据姓名查询 ~"<<endl;cout<<"~ (3)根据性别查询 ~"<<endl;cout<<"~ (4)退出 ~"<<endl;cout<<"************************"<<endl; if(m==1) 折半查找算法：for(int i=1;i<ST.length;i++)//使学号变为有序for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}int a=0;cout<<"输入要查找的学号"<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; // 置区间初值while (low<=high){mid=(low+high)/2;if(n==ST.r[mid].xuehao){cout<<ST.r[mid].xuehao<<""<<ST.r[mid].xingming<<""<<ST.r[mid].xingbei<<""<<ST.r[mid].chengji1<<""<<ST.r[mid].chengji2<<""<<ST.r[mid].zong<<endl;a=1;break;}else if(n<ST.r[mid].xuehao )high=mid-1; // 继续在前半区间进行查找elselow=mid+1; // 继续在后半区间进行查找顺序查找算法:cout<<"输入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i++){if(name==ST.r[i].xingming){cout<<ST.r[i].xuehao<<""<<ST.r[i].xingming<<""<<ST.r[i].xingbei<<""<<ST.r[i].chengji1<<""<<ST.r[i].chengji2<<""<<ST.r[i].zong<<endl;a=1;}1、插入排序每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。

查找和排序1．需求分析1．编写一个程序输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法查找关键字5的过程；2．编写一个程序输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用顺序方法查找关键字9的过程；3．编写一个程序实现直接插入排序算法，并输出{9，8，7，6，5，4，3，2，1，0}的排序过程；4．编写一个程序实现快速排序算法，并输出{6，8，7，9，0，1，3，2，4，5}的排序过程2．系统设计1．静态查找表的抽象数据类型定义：ADT StaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。

各个数据元素均含有类型相同，可惟一标识数据元素的关键字数据关系R：数据元素同属一个集合基本操作P：Create(&ST,n)操作结果：构造一个含n个数据元素的静态查找表STDestroy(&ST)初始条件：静态查找表ST存在操作结果：销毁表STSearch(ST,key)初始条件：静态查找表ST存在，key为和关键字类型相同的给定值操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”Traverse(ST,V isit())初始条件：静态查找表ST存在，Visit是对元素操作的应用函数操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次。

一旦Visit()失败，则操作失败}ADT StaticSearchTable3．调试分析（1）要在适当的位置调用Print函数，以正确显示排序过程中顺序表的变化（2）算法的时间复杂度分析：顺序查找：T(n)=O(n)折半查找：T(n)=O(logn)直接插入排序：T(n)=O(n2)快速排序：T(n)=O(nlogn)4．测试结果用需求分析中的测试数据顺序查找：顺序表3，6，2，10，1，8，5，7，4，9，查找5折半查找：顺序表1，2，3，4，5，6，7，8，9，10，查找9直接插入排序：顺序表9，8，7，6，5，4，3，2，1，0，从小到大排序快速排序：顺序表6，8，7，9，0，1，3，2，4，5，从小到大排序5．用户手册（1）输入表长；（2）依次输入建立顺序表；（3）查找：输入要查找的关键字（4）回车输出，查找为下标的移动过程；排序为顺序表的变化过程6．附录源程序：（1）顺序查找#include <stdio.h>#include <stdlib.h>#define ST_INIT_SIZE 200#define EQ(a,b) ((a)==(b))#define OVERFLOW -2typedef int KeyType;typedef struct{KeyType key;}ElemType;typedef struct{ElemType *elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空int length;//表长度}SSTable;void InitST(SSTable &ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}void CreateST(SSTable &ST){int i;printf("输入表长:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}void PrintST(SSTable ST){int i;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}int Search_Seq(SSTable ST,KeyType key){//在顺序表ST中顺序查找其关键字等于key的数据元素//若找到则函数值为该元素在表中的位置,否则为0int i;ST.elem[0].key=key;printf("下标:");for(i=ST.length;!EQ(ST.elem[i].key,key);--i)printf("%d→",i);//从后往前找return i;}void main(){SSTable ST;KeyType key;InitST(ST);CreateST(ST);printf("顺序查找表:");PrintST(ST);printf("输入要查找的关键字:");scanf("%d",&key);int found=Search_Seq(ST,key);if(found)printf("找到,为第%d个数据\n",found);else printf("没有找到!\n");}（2）折半查找#include <stdio.h>#include <stdlib.h>#define ST_INIT_SIZE 200#define EQ(a,b) ((a)==(b))#define LT(a,b) ((a)<(b))#define OVERFLOW -2typedef int KeyType;typedef struct{KeyType key;}ElemType;typedef struct{ElemType *elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空int length;//表长度}SSTable;void InitST(SSTable &ST){ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));if(!ST.elem)exit(OVERFLOW);ST.length=0;}void CreateST(SSTable &ST){int i;printf("输入表长:");scanf("%d",&ST.length);for(i=1;i<=ST.length;i++)scanf("%d",&ST.elem[i].key);}void PrintST(SSTable ST){int i;for(i=1;i<=ST.length;i++)printf("%2d",ST.elem[i].key);printf("\n");}int Search_Bin(SSTable ST,KeyType key){//在有序表ST中折半查找其关键字等于key的数据元素//若找到,则函数值为该元素在表中的位置,否则为0int low,high,mid;low=1;high=ST.length;//置区间初值printf("下标:");while(low<=high){mid=(low+high)/2;printf("%d→",mid);if(EQ(key,ST.elem[mid].key))return mid;//找到待查元素else if(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找else low=mid+1;}return 0;//顺序表中不存在待查元素}void main(){SSTable ST;KeyType key;InitST(ST);CreateST(ST);printf("顺序查找表:");PrintST(ST);printf("输入要查找的关键字:");scanf("%d",&key);int found=Search_Bin(ST,key);if(found)printf("找到,为第%d个数据\n",found);else printf("没有找到!\n");}（3）直接插入排序#include <stdio.h>#define MAXSIZE 20#define LT(a,b) ((a)<(b))typedef int KeyType;typedef struct{KeyType key;}RedType;//记录类型typedef struct{RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元int length;//顺序表长度}SqList;//顺序表类型void CreateSq(SqList &L){int i;printf("输入表长:");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}void PrintSq(SqList L){int i;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}void InsertSort(SqList &L){//对顺序表L作直接插入排序int i,j;printf("排序过程:\n");for(i=2;i<=L.length;++i){if(LT(L.r[i].key,L.r[i-1].key)){//"<",需将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}PrintSq(L);}}//InsertSortvoid main(){SqList L;CreateSq(L);printf("原始顺序表:");PrintSq(L);InsertSort(L);printf("排序后的顺序表:");PrintSq(L);}（4）快速排序#include <stdio.h>#define MAXSIZE 20typedef int KeyType;typedef struct{KeyType key;}RedType;//记录类型typedef struct{RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元int length;//顺序表长度}SqList;//顺序表类型void CreateSq(SqList &L){int i;printf("输入表长:");scanf("%d",&L.length);for(i=1;i<=L.length;i++)scanf("%d",&L.r[i].key);}void PrintSq(SqList L){int i;for(i=1;i<=L.length;i++)printf("%2d",L.r[i].key);printf("\n");}int Partition(SqList &L,int low,int high){//交换顺序表L中子表r[low…high]的记录,枢轴记录到位,并返回其所在位置, //此时在它之前/后的记录均不大/小于它int pivotkey;L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录pivotkey=L.r[low].key;//枢轴记录关键字while(low<high){//从表的两端交替地向中间扫描while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端}L.r[low]=L.r[0];//枢轴记录到位PrintSq(L);return low;//返回枢轴位置}//Partitionvoid QSort(SqList &L,int low,int high){//对顺序表L中的子序列L.r[low…high]作快速排序int pivotloc;if(low<high){//长度大于1pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}//QSortvoid QuickSort(SqList &L){//对顺序表L作快速排序printf("排序过程:\n");QSort(L,1,L.length);}//QuickSortvoid main(){SqList L;CreateSq(L);printf("原始顺序表:");PrintSq(L);QuickSort(L);printf("快速排序后的顺序表:");PrintSq(L);}。

数据结构实验六查找与排序班级学号姓名分数一、实验目的：1、掌握各种排序方法的基本思想、排序过程、算法实现2、能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方二、实验要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。

比较各种算法的运行速度。

三、实验内容及分析：比较各种算法的运行速度运行速度比较：直接排序冒泡排序直接插入冒泡排序快速排序时间复杂度 O(n2)，其中快速排序效率较高其它的效率差不多堆排序归并排序时间复杂度 (nlogn) ,平均效率都很高四、程序的调试及运行结果直接插入排序冒泡法排序快速排序直接选择排序堆排序归并排序五、程序代码#include"stdio.h"#include"stdlib.h"#define Max 100 //假设文件长度typedef struct{ //定义记录类型int key; //关键字项}RecType;typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵int n; //顺序表实际的长度//==========直接插入排序法======void InsertSort(SeqList R){ //对顺序表R中的记录R[1‥n]按递增序进行插入排序int i,j;for(i=2;i<=n;i++) //依次插入R[2]，……，R[n]if(R[i].key<R[i-1].key){ //若R[i].key大于等于有序区中所有的keys，则R[i]留在原位R[0]=R[i];j=i-1; //R[0]是R[i]的副本do{ //从右向左在有序区R[1‥i-1]中查找R[i] 的位置R[j+1]=R[j]; //将关键字大于R[i].key的记录后移j--;}while(R[0].key<R[j].key); //当R[i].key≥R[j].key 是终止R[j+1]=R[0]; //R[i]插入到正确的位置上}//endif}//==========冒泡排序=======typedef enum {FALSE,TRUE} Boolean; //FALSE为0，TRUE为1void BubbleSort(SeqList R) { //自下向上扫描对R做冒泡排序int i,j; Boolean exchange; //交换标志for(i=1;i<n;i++) { //最多做n-1趟排序exchange=FALSE; //本趟排序开始前，交换标志应为假for(j=n-1;j>=i;j--) //对当前无序区R[i‥n] 自下向上扫描if(R[j+1].key<R[j].key){ //两两比较，满足条件交换记录R[0]=R[j+1]; //R[0]不是哨兵，仅做暂存单元R[j+1]=R[j];R[j]=R[0];exchange=TRUE; //发生了交换，故将交换标志置为真}if(! exchange) //本趟排序未发生交换，提前终止算法return;}// endfor（为循环）}//1.========一次划分函数=====int Partition(SeqList R,int i,int j){ // 对R[i‥j]做一次划分，并返回基准记录的位置RecType pivot=R[i]; //用第一个记录作为基准while(i<j) { //从区间两端交替向中间扫描，直到i=jwhile(i<j &&R[j].key>=pivot.key) //基准记录pivot相当与在位置i上j--; //从右向左扫描，查找第一个关键字小于pivot.key的记录R[j]if(i<j) //若找到的R[j].key < pivot.key，则R[i++]=R[j]; //交换R[i]和R[j]，交换后i指针加1while(i<j &&R[i].key<=pivot.key) //基准记录pivot相当与在位置j上i++; //从左向右扫描，查找第一个关键字小于pivot.key的记录R[i]if(i<j) //若找到的R[i].key > pivot.key，则R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1}R[i]=pivot; //此时，i=j，基准记录已被最后定位return i; //返回基准记录的位置}//2.=====快速排序===========void QuickSort(SeqList R,int low,int high){ //R[low..high]快速排序int pivotpos; //划分后基准记录的位置if(low<high) { //仅当区间长度大于1时才排序pivotpos=Partition(R,low,high); //对R[low..high]做一次划分，得到基准记录的位置QuickSort(R,low,pivotpos-1); //对左区间递归排序QuickSort(R,pivotpos+1,high); //对右区间递归排序}}//======直接选择排序========void SelectSort(SeqList R){int i,j,k;for(i=1;i<n;i++){ //做第i趟排序（1≤i≤n-1）k=i;for(j=i+1;j<=n;j++) //在当前无序区R[i‥n]中选key最小的记录R[k] if(R[j].key<R[k].key)k=j; //k记下目前找到的最小关键字所在的位置if(k!=i) { // //交换R[i]和R[k]R[0]=R[i];R[i]=R[k];R[k]=R[0];} //endif} //endfor}//==========大根堆调整函数=======void Heapify( SeqList R,int low,int high){ // 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质int large; //large指向调整结点的左、右孩子结点中关键字较大者RecType temp=R[low]; //暂存调整结点for(large=2*low; large<=high;large*=2){ //R[low]是当前调整结点//若large>high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子if(large<high && R[large].key<R[large+1].key)large++; //若R[low]的右孩子存在且关键字大于左兄弟，则令large指向它//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者if(temp.key>=R[large].key) //temp始终对应R[low]break; //当前调整结点不小于其孩子结点的关键字，结束调整R[low]=R[large]; //相当于交换了R[low]和R[large]low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置 }R[low]=temp; //将被调整结点放入最终位置上}//==========构造大根堆==========void BuildHeap(SeqList R){ //将初始文件R[1..n]构造为堆int i;for(i=n/2;i>0;i--)Heapify(R,i,n); //将R[i..n]调整为大根堆}//==========堆排序===========void HeapSort(SeqList R){ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元int i;BuildHeap(R); //将R[1..n]构造为初始大根堆for(i=n;i>1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。

实验六查找
一、实验目的：
1．掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析。

2．掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。

二、实验内容：
1．将（45，24，55，12，37，53，60，28，40，70）中关键字依次插入初态为空的二叉排序树中，给出树的中序序列。

2．设计一组随机数据输入，分别对线性表进行顺序查找；选择一种合适排序算法排序，排序后对线性表采用折半查找（递归和非递归）。

3．实现直接插入排序、快速排序、归并排序算法。

三、实验要求：
1. 根据实验内容编程，上机调试、得出正确的运行程序。

2．写出实验报告（包括源程序和运行结果）。

五、主要算法及其流程图
六、输入数据和运行结果
七、算法复杂度（时间和空间）
八、实验小结。

查找排序实验报告一、实验目的本次实验的主要目的是深入理解和比较不同的查找和排序算法在性能和效率方面的差异。

通过实际编程实现和测试，掌握常见查找排序算法的原理和应用场景，为今后在实际编程中能够选择合适的算法解决问题提供实践经验。

二、实验环境本次实验使用的编程语言为 Python，开发环境为 PyCharm。

计算机配置为：处理器_____，内存_____，操作系统_____。

三、实验内容1、查找算法顺序查找二分查找2、排序算法冒泡排序插入排序选择排序快速排序四、算法原理1、顺序查找顺序查找是一种最简单的查找算法。

它从数组的一端开始，依次比较每个元素，直到找到目标元素或者遍历完整个数组。

其时间复杂度为 O(n)，在最坏情况下需要遍历整个数组。

2、二分查找二分查找适用于已排序的数组。

它通过不断将数组中间的元素与目标元素进行比较，将查找范围缩小为原来的一半，直到找到目标元素或者确定目标元素不存在。

其时间复杂度为 O(log n)，效率较高。

3、冒泡排序冒泡排序通过反复比较相邻的两个元素并交换它们的位置，将最大的元素逐步“浮”到数组的末尾。

每次遍历都能确定一个最大的元素，经过 n-1 次遍历完成排序。

其时间复杂度为 O(n^2)。

4、插入排序插入排序将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

其时间复杂度在最坏情况下为 O(n^2)，但在接近有序的情况下性能较好。

5、选择排序选择排序每次从待排序数组中选择最小的元素，与当前位置的元素交换。

经过 n-1 次选择完成排序。

其时间复杂度为 O(n^2)。

6、快速排序快速排序采用分治的思想，选择一个基准元素，将数组分为小于基准和大于基准两部分，然后对这两部分分别递归排序。

其平均时间复杂度为 O(n log n)，在大多数情况下性能优异。

五、实验步骤1、算法实现使用Python 语言实现上述六种查找排序算法，并分别封装成函数，以便后续调用和测试。

附件（四）深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：查找排序实验.学院：计算机与软件学院专业：指导教师：报告人：学号：班级：实验时间：实验报告提交时间：教务处制①②③④Problem B: 数据结构实验--二叉排序树之查找QSort(a,1,1);④(①b)low=4;high=5;6 22 55 111 333 444↑↑privotloc=4;a. QSort(a,low,pivotloc-1);QSort(a,4,3);b. QSort(a,pivotloc+1,high);QSort(a,5,5);排序完毕。

流程图：四、实验结论：1、根据你完成的每个实验要求，给出相应的实验结果图，并结合图来解析运行过程2、如果运行过程简单，只要贴出VC运行的结果图。

3、如果无结果图，有网站的判定结果，贴出相应结果Contest1657 - DS实验--静态查找Problem A: 数据结构实验--静态查找之顺序查找Sample Input833 66 22 88 11 27 44 553221199Sample Output35errorProblem B: 数据结构实验--静态查找之折半查找Sampl e Input811 22 33 44 55 66 77 883228899Sampl e Output28errorProblem C: 数据结构实验--静态查找之顺序索引查找Sampl e Input1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53322 48 86613548405390Sampl e Output3-4error12-8error18-9errorContest1040 - DS实验--动态查找Problem A: 数据结构实验--二叉排序树之创建和插入Sample Input1622 33 55 66 11 443775010Sample Output11 22 33 44 55 6611 22 33 44 55 66 7711 22 33 44 50 55 66 7710 11 22 33 44 50 55 66 77Problem B: 数据结构实验--二叉排序树之查找Sample Input1622 33 55 66 11 44711223344556677Sample Output11 22 33 44 55 66212434-1Problem C: 数据结构实验--二叉排序树之删除Sample Input1622 33 55 66 11 443662277Sample Output11 22 33 44 55 6611 22 33 44 5511 33 44 5511 33 44 55Contest1050 - DS实验--哈希查找Problem A: 数据结构实验--哈希查找Sample Input11 23 39 48 75 626395252636352Sample Output6 1error8 1error8 18 2Contest1060 - DS实验--排序算法Problem A: 数据结构实验--希尔排序Sample Input6111 22 6 444 333 55877 555 33 1 444 77 666 2222Sample Output6 22 55 111 333 4441 33 77 77 444 555 666 2222Problem B: 数据结构实验--快速排序Sample Input26111 22 6 444 333 55877 555 33 1 444 77 666 2222Sample Output6 22 55 111 333 4441 33 77 77 444 555 666 2222。