查找、排序的应用实验

查找和排序算法实验报告一、实验目的本次实验的主要目的是深入理解和掌握常见的查找和排序算法，通过实际编程实现和性能比较，分析不同算法在不同数据规模和数据分布情况下的效率和优劣，为在实际应用中选择合适的算法提供依据。

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

实验中使用的操作系统为 Windows 10。

三、实验内容（一）查找算法1、顺序查找顺序查找是最基本的查找算法，从数组的一端开始，逐个比较元素，直到找到目标元素或遍历完整个数组。

｀｀｀pythondef sequential_search(arr, target)：for i in range(len(arr)）：if arri ＝＝ target:return ireturn －1｀｀｀2、二分查找二分查找要求数组是已排序的。

通过不断将数组中间的元素与目标元素比较，缩小查找范围，直到找到目标元素或确定目标元素不存在。

｀｀｀pythondef binary_search(arr, target)：low ＝ 0high ＝ len(arr) 1while low ＜＝ high:mid ＝（low ＋ high) ／／ 2if arrmid ＝＝ target:return midelif arrmid ＜ target:low ＝ mid ＋ 1else:high ＝ mid 1return －1｀｀｀（二）排序算法1、冒泡排序冒泡排序通过反复比较相邻的元素并交换位置，将最大的元素逐步“浮”到数组的末尾。

｀｀｀pythondef bubble_sort(arr)：n ＝ len(arr)for i in range(n)：for j in range(0, n i 1)：if arrj ＞ arrj ＋ 1 ：arrj, arrj ＋ 1 ＝ arrj ＋ 1, arrj｀｀｀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. 理解排序算法的基本原理和特点。

2. 掌握几种常用的排序算法，如冒泡排序、选择排序、插入排序等。

3. 学习查找算法的基本原理和特点。

4. 掌握几种常用的查找算法，如顺序查找、二分查找等。

5. 通过实验，提高对排序和查找算法的运用能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 实现冒泡排序、选择排序、插入排序等排序算法。

2. 实现顺序查找、二分查找等查找算法。

3. 对一组数据进行排序和查找操作，并记录实验数据。

四、实验步骤1. 设计排序算法（1）冒泡排序冒泡排序的基本思想是：通过相邻元素的比较和交换，将较大的元素逐步移动到数组的末尾，从而实现排序。

（2）选择排序选择排序的基本思想是：每次从待排序的数组中找到最小（或最大）的元素，将其放到序列的起始位置，直到全部排序完成。

（3）插入排序插入排序的基本思想是：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

2. 设计查找算法（1）顺序查找顺序查找的基本思想是：从数组的第一个元素开始，依次将元素与要查找的值进行比较，直到找到目标元素或遍历完整个数组。

（2）二分查找二分查找的基本思想是：将数组分成两部分，每次比较查找值与中间元素的值，根据比较结果确定查找值的所在区间，直到找到目标元素或区间为空。

3. 编写实验代码```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]def selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i] def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keydef sequential_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1def binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1# 测试数据arr = [64, 34, 25, 12, 22, 11, 90]# 排序bubble_sort(arr)print("冒泡排序结果：", arr)selection_sort(arr.copy())print("选择排序结果：", arr)insertion_sort(arr.copy())print("插入排序结果：", arr)# 查找target = 22print("顺序查找结果：", sequential_search(arr, target)) target = 90print("二分查找结果：", binary_search(arr, target))```4. 实验结果与分析通过实验，我们得到了以下结果：（1）冒泡排序结果：[11, 12, 22, 25, 34, 64, 90]（2）选择排序结果：[11, 12, 22, 25, 34, 64, 90]（3）插入排序结果：[11, 12, 22, 25, 34, 64, 90]（4）顺序查找结果：2（5）二分查找结果：6从实验结果可以看出，冒泡排序、选择排序和插入排序都能够对数据进行正确的排序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：学号：姓名：实验报告要求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.不能太过死板，要灵活运用所学知识。

实验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个数据元素则按递增次序排列完成。