查找和排序的实现.doc

《查找和排序的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验:查找和排序的实现1.实验目的1）掌握折半查找,顺序查找和黄金比例查找的方法；2）掌握直接插入排序，折半插入排序和快速排序的方法。2.实验内容：(1)建立顺序表;(2）实现以下算法：输入要查询的值，经过顺序查找和折半查找还有黄金比例查找，找出该元素的位置。顺序表经过直接插入排序，折半插入排序和快速排序后输出。3.设计思想1．(非递减序列)顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若相等，则查找成功。2．(非递减序列)折半查找：以处于区间中间位置记录的关键字和给定值比较，若相

2、等则成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止3.(非递减序列)黄金比例查找：以处于区间黄金比例处（0.618）位置记录的关键字和给定值比较，注意，不能直接用mid=(low+high)*0.618，这样mid会溢出，应该改为mid=(high-low)*0.618+low。4.直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。它是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置

3、。直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。5.折半插入排序：是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。[6.快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成

4、有序序列。4.代码实现#include#include#defineLIST_INIT_SIZE100#defineLISTNCREMENT10typedefstructSqList{int*elem;intlength;intlistsize;}SqList;voidInitList_Sq(SqList&L)//数据结构初始化，构造空的表{L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.elem)ex

5、it(1);L.length=0;L.listsize=LIST_INIT_SIZE;}voidCreat(SqList&L)//建立顺序表{intn;cout<<"请输入存储的个数:";cin>>n;cout<<"请按非递减顺序输入元素:"<>L.elem[i];L.length=n;}intsearch_Seq(SqListL,intkey,int&d){//顺序查找L.elem[0]=key;inti;d=d+1;for(i=L.lengt

6、h;key!=L.elem[i];--i)d=d+1;returni;}inthalfserch(SqListL,intkey2,int&k){L.elem[0]=key2;intlow=1;inthigh;intmid;high=L.length;k=0;while(low<=high){mid=(low+high)/2;k=k+1;if(key2==L.elem[mid])returnmid;elseif(key2<=L.elem[mid])high=mid-1;elselow=mid+1;}retu

7、rn0;}intNewserch(SqListL,intkey,int&d){L.elem[0]=key;intlow=1;inthigh;intmid;high=L.length;d=0;while(low<=high){mid=(high-low)*0.618+low;d=d+1;if(key==L.elem[mid])returnmid;elseif(key<=L.elem[mid])high=mid-1;elselow=mid+1;}return0;}voidmain(){SqListL;cout

8、<<"创建顺序表"<>a;c=search_Seq(L,a,d);cout<<"做顺序查找的执行次数为："<