查找和排序的实现

1.实验目的

1）掌握折半查找,顺序查找和黄金比例查找的方法；

2）掌握直接插入排序，折半插入排序和快速排序的方法。

2. 实验内容： 

(1) 建立顺序表;

(2）实现以下算法：

输入要查询的值，经过顺序查找和折半查找还有黄金比例查找，找出该元素的位置。

顺序表经过直接插入排序，折半插入排序和快速排序后输出。

 3. 设计思想

1．(非递减序列)顺序查找：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若相等，则查找成功。

2．(非递减序列)折半查找：以处于区间中间位置记录的关键字和给定值比较，若相等则成功，如不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止

3. (非递减序列)黄金比例查找：以处于区间黄金比例处（0.618）位置记录的关键字和给定值比较，注意，不能直接用mid=(low+high)*0.618，这样mid会溢出，应该改为mid=(high-low)*0.618+low。

4.直接插入排序：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。它是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

5. 折半插入排序：是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。[

6.快速排序：通过一趟排序将要排序的数据分割成的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

4.代码实现

#include

#include

#define LIST_INIT_SIZE    100

#define LISTNCREMENT    10

typedef struct SqList

{

    int *elem;

    int length;

    int listsize;

}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;

cout<<"请输入存储的个数:";

cin>>n;

cout<<"请按非递减顺序输入元素:" < for(int i=1;i<=n;i++)

cin>>L.elem[i];

    L.length=n;

}    

int search_Seq(SqList L,int key,int &d){//顺序查找

   L.elem[0]=key;

   int i;

   d=d+1;

   for(i=L.length;key!=L.elem[i];--i)

       d=d+1;

       return i;

}

int halfserch(SqList L,int key2,int &k){

    L.elem[0]=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.elem[mid])

        return mid;

else if (key2<=L.elem[mid])

        high=mid-1;

    else low=mid+1;

    }

    return 0;

}

int Newserch(SqList L,int key,int &d){

    L.elem[0]=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.elem[mid])

        return mid;

else if (key<=L.elem[mid])

        high=mid-1;

    else low=mid+1;

    }

    return 0;

}

void main()

{

    SqList  L;

cout<<"创建顺序表"<    InitList_Sq(L);

    Creat(L);

    int a,b,c,d,e;

    d=0;

cout<<"请输入要查询的值:"< cin>>a;

    c=search_Seq(L,a,d);

cout<<"做顺序查找的执行次数为："< cout<<"经过顺序查找，您查询的元素位置是："<    b=halfserch(L,a,d);

cout<<"做折半查找的执行次数为："< cout<<"经过折半查找，您查询的元素位置是："<    e=Newserch(L,a,d);

cout<<"做折半查找的执行次数为："< cout<<"经过0.618查找，您查询的元素位置是："<}

5.运行与测试

第一组：

第二组：