数据结构实验六 查找及排序

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

二、实验环境本次实验使用的编程语言为 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、插入排序插入排序将未排序的元素逐个插入到已排序的部分中，保持已排序部分始终有序。

电子科技大学实验报告课程名称：数据结构与算法学生姓名：学号：点名序号：指导教师：实验地点：基础实验大楼实验时间： 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右边的表中。

5、设有序顺序表中的元素依次为017,094,154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908.试画出对其进行折半搜索时的判定树,并计算搜索成功的 平均搜索长度。
• Hash查找和Hash表的创建
– 常用Hash函数和解决冲突方法 – Hash表的创建与平均查找长度的计算 – 时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及
第一部分 查找
二分查找,Hash表
• 二分查找考点
– 条件：顺序存储,按关键字有序 – 时间复杂度分析（log2n） – 最多要比较的次数（㏒2n +1 ）,理由：n个结点的判定树的深度
与n个结点的完全二叉树深度相同。 – 折半查找的二叉判定树
例如：
1、请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个 记录的顺序表中进行二分查找,最大的比较次数是多少？
答：数据元素初始状态按关键字有序
最大比较次数应为㏒2n +1
2、设顺序表为{4, 6, 12, 38, 40, 67, 80}用二分法查找72,需要进行的比较次数为
（）
A、3 B、n-1 C、n+1
D、n
答案：A
3、试用于折半查找的表的存储方式及元素排列要求是顺序存储,按关键字有序。
4、对有10个元素的有序表,采用二分查找,需要比较4次方可找到的元素个数为 3。
➢ 稳定性：不稳定。反例如下：
221
2 领先于 2 排序前
122
2 落后于 2 排序后
不稳定！
❖ 堆(Heap)
堆是一棵完全二叉树,它的每一个结点满足： 若其有孩子,则该结点的值大于（或小于）孩子的值。

数据结构实验六查找与排序班级学号姓名分数一、实验目的：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趟。