查找和排序的实现

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.直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。它是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序属于稳定的排序，最坏时间复杂性为O(n2)，空间复杂度为O(1)。5. 折半插入排序：是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素

3、插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。6.快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。4.代码实现#include #include #define LIST_INIT_SIZE100#define LISTNCREMENT10typedef struct SqListint *elem;int length;int listsize

4、;SqList;void InitList_Sq(SqList &L)/数据结构初始化，构造空的表L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int);if(!L.elem) exit(1);L.length=0;L.listsize=LIST_INIT_SIZE;void Creat(SqList &L)/建立顺序表int n;coutn;cout请按非递减顺序输入元素: endl;for(int i=1;iL.elemi;L.length=n;int search_Seq(SqList L,int key,int &d)/顺序查找 L.elem0

5、=key; int i; d=d+1; for(i=L.length;key!=L.elemi;-i) d=d+1; return i; int halfserch(SqList L,int key2,int &k)L.elem0=key2; int low=1;int high;int mid;high=L.length;k=0;while(low=high)mid=(low+high)/2;k=k+1;if(key2=L.elemmid)return mid;else if (key2=L.elemmid)high=mid-1;else low=mid+1;return 0;int New

6、serch(SqList L,int key,int &d)L.elem0=key; int low=1;int high;int mid;high=L.length;d=0;while(low=high)mid=(high-low)*0.618+low;d=d+1;if(key=L.elemmid)return mid;else if (key=L.elemmid)high=mid-1;else low=mid+1;return 0;void main()SqList L;cout创建顺序表endl;InitList_Sq(L);Creat(L);int a,b,c,d,e;d=0;cout请输入要查询的值:a; c=search_Seq(L,a,d);cout做顺序查找的执行次数为：dendl;cout经过顺序查找，您查询的元素位置是：cendl; b=halfserch(L,a,d);cout做折半查找的执行次数为：dendl; cout经过折半查找，您