查找,排序的应用实验

实验六查找
一、实验目的：
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 语言实现上述六种查找排序算法，并分别封装成函数，以便后续调用和测试。

实验七查找、排序的应用一、实验目的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. 熟悉常用的查找和排序算法，掌握它们的原理和实现方法。

2. 提高编程能力，提高算法分析能力。

3. 通过实验验证查找和排序算法的性能。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 查找算法：二分查找、线性查找2. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序四、实验步骤1. 设计一个数据结构，用于存储待查找和排序的数据。

2. 实现二分查找算法，用于查找特定元素。

3. 实现线性查找算法，用于查找特定元素。

4. 实现冒泡排序、选择排序、插入排序、快速排序、归并排序算法，对数据进行排序。

5. 分别测试查找和排序算法的性能，记录时间消耗。

五、实验结果与分析1. 查找算法（1）二分查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为5（2）线性查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为52. 排序算法（1）冒泡排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（2）选择排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（3）插入排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（4）快速排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（5）归并排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]3. 性能测试（1）查找算法性能测试二分查找算法在数据量较大的情况下，查找效率明显优于线性查找算法。

（2）排序算法性能测试在数据量较大的情况下，快速排序和归并排序的性能明显优于冒泡排序、选择排序和插入排序。

排序和查找的实验报告实验报告：排序和查找引言排序和查找是计算机科学中非常重要的基本算法。

排序算法用于将一组数据按照一定的顺序排列，而查找算法则用于在已排序的数据中寻找特定的元素。

本实验旨在比较不同排序和查找算法的性能，并分析它们的优缺点。

实验设计为了比较不同排序算法的性能，我们选择了常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序。

我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。

在查找算法的比较实验中，我们选择了顺序查找和二分查找两种常见的算法。

同样地，我们使用相同的随机数据集对这些算法进行了测试，并记录了它们的执行时间和占用空间。

实验结果在排序算法的比较实验中，我们发现快速排序和归并排序在大多数情况下表现最好，它们的平均执行时间和空间占用都要优于其他排序算法。

而冒泡排序和插入排序则表现较差，它们的执行时间和空间占用相对较高。

在查找算法的比较实验中，二分查找明显优于顺序查找，尤其是在数据规模较大时。

二分查找的平均执行时间远远小于顺序查找，并且占用的空间也更少。

结论通过本实验的比较，我们得出了一些结论。

首先，快速排序和归并排序是较优的排序算法，可以在大多数情况下获得较好的性能。

其次，二分查找是一种高效的查找算法，特别适用于已排序的数据集。

最后，我们也发现了一些排序和查找算法的局限性，比如冒泡排序和插入排序在大数据规模下性能较差。

总的来说，本实验为我们提供了对排序和查找算法性能的深入了解，同时也为我们在实际应用中选择合适的算法提供了一定的参考。

希望我们的实验结果能够对相关领域的研究和应用有所帮助。

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：学号：姓名：实验报告要求1目的与要求:1）完整理解二叉排序树的基本概念;2) 掌握二叉排序树的建立、查找、插入和删除算法实现思想和基本应用方法；3）掌握二叉排序树的建立、查找、插入和删除算法实现的c语言编程技巧；4）完整理解有关排序的基本概念;5) 掌握各种排序方法的算法实现思想和存储表示方法；6）掌握所选排序方法的C语言编程技巧；7）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；8）认真书写实验报告,并按时提交。

2 实验内容或题目题目1：用C或C++语言设计实现二叉排序树的基本操作应用程序，功能包括：二叉排序树的建立，二叉排序树的查找，二叉排序树的插入，二叉排序树的删除。

程序实现后，用记录关键字序列：{55，59，45，23，72，109，89，112，48，2，3}进行正确性验证（在建立、删除、插入操作后要给出相应二叉排序树遍历结果）。

题目2：用C或C++语言设计实现快速排序方法的排序应用程序。

程序实现后，以待排序记录序列：{55，13，23，72，109，67，2，78, 23}进行正确性验证。

选做题目：用C或C++语言实现快速排序之外的其他算法，并以序列：{55，13，23，72，109，67，2，78,23}对程序进行正确性验证。

3 实验步骤与源程序（1）#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct Bstnode{int key;struct Bstnode *lchild,*rchild;}Bstnode,* Bstree;Bstree Create();Bstree Insert(Bstree tree,int key);Bstree Search(Bstree tree,int key);void Traverse(Bstree tree);Bstree Create(){int key; Bstree tree=NULL; scanf("%d",&key); while(key!=0){tree=Insert(tree,key);scanf("%d",&key);}return tree;}Bstree Insert(Bstree tree,int key){Bstree p=tree;Bstree s,f;while (p!=NULL){f=p;if(key==p->key) return tree;if(key<p->key) p=p->lchild;else p=p->rchild;}s=(Bstree)malloc(sizeof(Bstnode));s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree==NULL)return s;if(key<f->key)f->lchild=s;elsef->rchild=s;return tree;}Bstree Search(Bstree tree,int key){Bstree p=tree;int flag=0;while(p!=NULL){if(p->key==key){printf("查询到该节点！");flag=1;return(p);}if (key<p->key)p=p->lchild;elsep=p->rchild;}if(flag==0){printf("查询不到关键字为%d的节点！",key);return NULL;}}void Traverse(Bstree tree){if(tree){Traverse(tree->lchild);printf("%4d",tree->key);Traverse(tree->rchild);}}Bstree Delete(Bstree tree,int key){Bstree p=tree;Bstree f,s,q;f=NULL;while(p){//查找关键字为key的节点if(p->key==key)break;f=p;if(p->key>key)p=p->lchild;elsep=p->rchild;}if (p==NULL)return tree;if ((p->lchild==NULL)||(p->rchild==NULL)){if(f==NULL) if(p->lchild==NULL)tree=p->rchild;elseelse if (p->lchild==NULL)if(f->lchild==p)f->lchild=p->rchild;elsef->rchild=p->rchild;else if(f->lchild==p)f->lchild=p->lchild;elsef->lchild=p->lchild;free(p);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}if(q==p) q->lchild=s->lchild;p->key=s->key;free(s);}return tree;}void main(){Bstree tree,p;int key1,key2,key3;int select,flag;printf("############################################\n"); printf("|* 欢迎您使用本系统 *|\n"); printf("|******************************************|\n"); printf("|* 1.创建二叉排序树 *|\n"); printf("|* 2.插入 *|\n"); printf("|* 3.查找 *|\n"); printf("|* 4.遍历 *|\n"); printf("|* 5.删除 *|\n"); printf("|* 6.退出 *|\n"); printf("********************************************\n"); while(select!=6){printf("选择的功能：");scanf("%d",&select);switch(select)case 1: printf("请输入节点信息(0为结束符):\n");tree=Create();break;case 2: printf("插入一个新的节点:");scanf("%d",&key1);Insert(tree,key1);printf("插入后得序列为:\n");Traverse(tree);printf("\n");break;case 3: printf("输入查找的数据:");scanf("%d",&key2);p=Search(tree,key2);printf("\n");break;case 4: printf("遍历所得序列为:\n");Traverse(tree);printf("\n");break;case 5: printf("输入删除的数据:");scanf("%d",&key3);tree=Delete(tree,key3);printf("删除后遍历所得序列:\n");Traverse(tree);printf("\n");break;case 6: printf("谢谢您的使用，再见！\n");flag=0;break;default:printf("输入错误,请重新输入\n");break;}}}（2）#include<stdio.h>typedef int KeyType;typedef int OtherType;typedef struct{KeyType key;}RecordType;int QKPass(RecordType r[],int left,int right){RecordType x;int low=left;int high=right;while(low<high){while(low<high&&r[high].key>=x.key){high--;}if(low<high){r[low]=r[high];low++;}while(low<high&&r[low].key<x.key){low++;}if(low<high){r[high]=r[low];high--;}}r[low]=x;return low;}void QKSort(RecordType r[],int low,int high) {if(low<high){int pos=QKPass(r,low,high);QKSort(r,low,pos-1);QKSort(r,pos+1,high);}}void main(){RecordType r[9];printf("请输入要排序的数据:\n");for(int i=0;i<9;i++){scanf("%d",&r[i]);}QKSort(r,0,8);printf("快速排序结果为:\n");{printf("%d ",r[i]);}printf("\n");}4 测试数据与实验结果（可以抓图粘贴）（1）（2）5 结果分析与实验体会本次试验是有关查找和排序的一些操作，要求理解二叉排序树的基本概念并实现二叉树的建立、查找、插入和删除算法。

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：软件112学号：2011122635姓名：排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。

2 实验内容或题目题目：对记录序列（查找表）：{287，109，063，930，589，184，505，269,008，083}分别实现如下操作：1)分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2)对上述纪录列表排好序，然后对其进行折半查找或顺序查找；3 实验步骤与源程序#include "stdio.h"#include "stdlib.h"#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef struct{KeyType key;}RecordType;typedef struct{RecordType r[LIST_SIZE+1];int length;}RecordList;void seqSearch(RecordList *l){KeyType k; int i;printf("请输出要查询的元素k:");fflush(stdin);scanf("%d",&k);i=l->length;while (i>=0&&l->r[i].key!=k)i--;printf("该元素的位置是");printf("%d",i+1);//cout<<"该元素在图中第"<<i<<"个位置"<<endl; printf("\n");}void BinSrch(RecordList *l){KeyType q;int mid;printf("请输入要查询的元素k:");fflush(stdin);scanf("%d",&q);int low=1;int high=l->length;while(low<=high){mid=(low+high)/2;if(q==l->r[mid].key){printf("该元素的位置为:");printf("%d",mid+1);//注意不能随便使用&printf("\n");break;}else if(q<l->r[mid].key)high=mid-1;elselow=mid+1;}}void inputkey(RecordList *l){int i;printf("请输入线性表长度:");//遇到错误：1.print用法scanf("%d",&(l->length));//&将变量的地址赋值，而不是变量的值for(i=1;i<=l->length ;i++){printf("请输入第%d个元素的值:",i);fflush(stdin);scanf("%d",&(l->r[i].key));}}void InsSort(RecordList *l){for(int i=2;i<=l->length;i++){l->r[0].key=l->r[i].key;int j=i-1;while(l->r[0].key<l->r[j].key){l->r[j+1].key=l->r[j].key;j=j-1;}l->r[j+1].key=l->r[0].key;}}//直接插入排序void BubbleSort(RecordList *l){int x,i,n,change,j;n=l->length;change=TRUE;for(i=1;i<=n-1&&change;++i){change=FALSE;for(j=1;j<=n-i;++j)if(l->r[j].key>l->r[j+1].key){x=l->r[j].key;l->r[j].key=l->r[j+1].key ;l->r[j+1].key=x;change=TRUE;}}}//冒泡排序法int QKPass(RecordList *l,int left,int right) {int x;x=l->r[left].key ;int low=left;int high=right;while(low<high){while(low<high&&l->r[high].key>=x)high--;if(low<high){l->r[low].key=l->r[high].key;low++;}while(low<high&&l->r[low].key<=x)low++;if(low<high){l->r[high].key=l->r[low].key;high--;}}l->r[low].key=x;return(low);}void QKSort(RecordList *l,int low,int high){int pos;if(low<high){pos=QKPass(l,low,high);QKSort(l,low,pos-1);QKSort(l,pos+1,high);}}//快速排序void SelectSort(RecordList *l){int n,i,k,j,x;n=l->length;for(i=1;i<=n-1;++i){k=i;for(j=i+1;j<=n;++j)if(l->r[j].key<l->r[k].key) k=j;if(k!=i){x=l->r[i].key;l->r[i].key=l->r[k].key;l->r[k].key=x;} }}void output(RecordList *l){for(int i=1;i<=l->length;i++){printf("%d",l->r[i].key);printf("\n");}}void main(){RecordList *l,*t,*m,*n;l=(RecordList *)malloc(sizeof(RecordList));int low;int high;int flag=1;int xuanze;while(flag!=0){printf("####################################################\n");printf("###### 请选择你要进行的操作! #########\n");printf("###### 1.直接插入排序; #########\n");printf("###### 2.冒泡排序; #########\n");printf("###### 3.快速排序; #########\n");printf("###### 4.简单选择排序; #########\n");printf("###### 5.顺序查找; #########\n");printf("###### 6.折半查找; #########\n");printf("###### 7.退出! #########\n");printf("####################################################\n");scanf("%d",&xuanze);switch(xuanze){case 1:inputkey(l);InsSort(l);printf("直接插入排序结果是:\n");output(l);break;case 2:inputkey(l);BubbleSort(l);printf("冒泡排序结果是:\n");output(l);break;case 3:inputkey(l);low=1;high=l->length;QKSort(l,low,high);printf("快速排序结果是:\n");output(l);break;case 4:inputkey(l);SelectSort(l);printf("简单选择排序结果是:\n");output(l);break;case 5:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);seqSearch(l);break;case 6:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);break;BinSrch(l);case 7:flag=0;break;}}}4 测试数据与实验结果（可以抓图粘贴）《数据结构》实验报告- 10 -5 结果分析与实验体会1.编程时要细心，避免不必要的错误；2.要先熟悉书本上的内容，否则编译会有困难；3.不能太过死板，要灵活运用所学知识。

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：实验4 查找、排序的应用班级：学号：姓名：实验4 查找、排序的应用实验目的和要求1.熟悉查找表的存储结构。

2.熟练掌握循序查找和二分查找方法。

3.熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率有进一步的了解。

4.实现两种以上的简单排序和快速排序、比较它们的时间效率。

5.要求独立完成实验内容（提交程序清单、相关实验数据及运行结果）；6.要求认真书写实验报告,并按时提交。

实验环境Turbo C 或VC++实验学时4学时，必做实验实验内容和步骤l、产生n个整数并存于数组r[1..n]中。

对主要查找算法（顺序查找、折半查找）和排序算法（直接插入排序、冒泡排序、快速排序、简单选择排序）进行实验比较，计算出平均比较次数、平均移动次数。

2、对实验结果数据进行对比分析。

1. #include <iostream>using namespace std;int count;int SepSearch(int r[], int key,int len) //顺序查找{int i;count=0;i=len;while(key!=r[i]){i--;count++;}return(i);}int BinSrch(int r[],int key,int len) //折半查找{int low,high,mid;low=1;high=len;count=0;while(low<=high){ count++;mid=(low+high)/2;if(key==r[mid]) return(mid);else if(key<r[mid]) high=mid-1;else low=mid+1;}return(0);}void BiInsertsort(int r[], int n) //插入排序（折半）{count=0;for(int i=2;i<=n;i++){if (r[i]<r[i-1]){r[0] = r[i];int low=1,high=i-1;while (low<=high){count++;int mid=(low+high)/2;if (r[0]<r[mid])high=mid-1;else low = mid+1;}int j;for (j=i-1;j>high;j--){r[j+1] = r[j];count++;}r[j+1] = r[0];}}for(int k=1;k<=n;k++)printf("%d ",r[k]);printf("\n");}void BubbleSort(int r[], int n) //冒泡排序{count=0;int i;int temp,exchange,bound;exchange=n;while (exchange) //仅当上一趟排序有记录交换才进行本趟排序{bound=exchange;exchange=0;for (int j=1; j<bound; j++)if (r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;count++;}}for( i=1;i<=n;i++)printf("%d ",r[i]);printf("\n");}int Partition(int r[], int first, int end) //快速排序一次划分{int i=first;int j=end;r[0]=r[first];count=1;while (i<j){while (i<j && r[0]<= r[j]) j--; //右侧扫描r[i]=r[j];while (i<j && r[i]<= r[0]) i++; //左侧扫描r[j]=r[i];}r[i]=r[0];return i; //i为轴值记录的最终位置}void QuickSort(int r[], int first, int end) //快速排序{count++;if (first<end){int pivot=Partition(r, first, end);QuickSort(r, first, pivot-1); //递归地对左侧子序列进行快速排序QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序}}void SelectSort(int r[ ], int n) //简单选择排序{count=0;int i,j,index,temp;for (i=1; i<n; i++){index=i;for (j=i+1; j<=n; j++){count++;if (r[j]<r[index]) index=j;}if (index!=i){temp=r[i];r[i]=r[index];r[index]=temp;}}for(i=1;i<=n;i++)printf("%d ",r[i]);printf("\n");}void main(){const int numv=12;inta[3][numv]={{0,6,13,19,23,37,39,41,45,48,58,86},{0,86,58,48,45,41,39,37,23,19,13,6},{0,23,13,48,86,19, 6,41,58,37,45,39}};int z1[numv],z2[numv];int m,n,i,j;int s1;printf("请选择测试数据类:1 正序2 逆序3 随机[ 若跳出,请按4 ]\n");scanf("%d",&m);while(m>0&&m<4){printf("请选择操作算法：1 直接插入排序2 冒泡排序3 快速排序 4 简单选择排序5顺序查找6 折半查找\n");scanf("%d",&n);switch(n){case 1:printf("直接插入排序前:\n");for(j=1;j<numv;j++)printf("%d ",a[m-1][j]);printf("\n");printf("直接插入排序结果为:\n");BiInsertsort(a[m-1],numv-1);printf("移动了""%d""次\n",count);break;case 2:printf("冒泡排序前:\n");for( j=1;j<numv;j++)printf("%d ",a[m-1][j]);printf("\n");printf("冒泡排序结果为:\n");BubbleSort(a[m-1], numv-1);printf("移动了""%d""次\n",count);break;case 3:printf("快速排序前:\n");for( j=1;j<numv;j++)printf("%d ",a[m-1][j]);printf("\n");printf("快速排序结果为:\n");QuickSort(a[m-1],0,numv-1);for(i=1;i<numv;i++)printf("%d ",a[m-1][i]);printf("\n");printf("移动了""%d""次\n",count);break;case 4:printf("简单选择排序前:\n");for( j=1;j<numv;j++)printf("%d ",a[m-1][j]);printf("\n");printf("简单选择排序结果为:\n");SelectSort(a[m-1],numv-1);printf("移动了""%d""次\n",count);break;case 5:printf("请输入查找的数:\n");scanf("%d\n",&s1);i=SepSearch(a[m-1], s1,numv-1);printf("用顺序查找法查找数""%d""在第""%d""位,""比较了""%d""次\n",s1,i+1,count); break;case 6:printf("请输入查找的数:\n");scanf("%d\n",&s1);j=BinSrch(a[m-1], s1,numv-1);printf("用折半查找法查找数""%d""在第""%d""位,""比较了""%d""次\n",s1,i+1,count);break;default:printf("输入错误!\n");}m=0;printf("请选择测试数据类型:1 正序2逆序3随机[ 若跳出,请按4 ]:\n");scanf("%d",&m);}if(m==4) printf("(*^__^*) 再见!\n");else printf("输入错误!\n");}实验结果：（1）直接插入排序：（2）冒泡排序：（3）快速排序：(3)快速排序（4）简单选择排序（5）顺序查找（6）折半查找2.1 顺《数据结构》实验报告- 10 -2结果分析（1）几种排序法的比较如下表：(2)顺序查找平均查找长度:ASL=1/2(n+1)(3)折半法平均查找长度：ASL= (n+1)/2*log2(n+1)-1折半法查找方法优点是比较次数少，查找速度快，平均性能好，但要求查找的表为有序，且插入删除困难。

实验8：查找、排序一、实验目的深入了解各种内部排序方法及效率分析。

二、问题描述各种内部排序算法的时间复杂度分析，试通过随机数据比较算法的关键字比较次数和关键字移动次数。

三、实验要求1、对起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序这六种常用排序算法进行比较。

2、待排序表的表长不超过100；其中数据用伪随机数产生程序产生。

3、至少要用6组不同的输入数据做比较。

4、要对实验结果做简单分析。

四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C++ 程序集成环境五、实验步骤1、根据问题描述写出基本算法。

2、设计六种排序算法并用适当语言实现。

3、输入几组随机数据，并对其关键字比较次数和关键字移动次数的比较。

4、对结果进行分析。

5、进行总结。

六种实验算法的基本思想：（1）直接插入排序的基本思想是：当插入第i个数据元素k时，由前i-1个数据元素组成已排序的数据元素序列，将k的关键字与序列中各数据元素的关键字依次进行比较后，找到该插入位置j，并将第j以及后面的数据元素顺序后移一个位置，然后将k插入到位置j，使得插入后的数据元素序列仍是排序的。

（2）希尔排序的基本思想是：先将整个待排序记录序列按给定的下标增量进行分组，并对组内的记录采用直接插入排序，再减小下标增量，即每组包含的记录增多，再继续对每组组内的记录采用直接插入排序；以此类推，当下标增量减小到1时，整个待排序记录已成为一组，再对全体待排序记录进行一次直接插入排序即可完成排序工作。

（3）冒泡排序的基本思想是：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。

对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。

然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。

（4）选择排序的基本思想是：设有N个数据元素的序列，第一趟排序，比较N个数据元素，选择关键字最小的数据元素，将其交换到序列的第1个位置上；第2趟排序，在余下的N-1个数据元素中，再选取关键字最小的数据元素，交换到序列的第2个位置上；继续进行，经过N-1趟排序，N个数据元素则按递增次序排列完成。