实   验   报   告

实验原理：

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

    假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

   1）设置两个变量I、J，排序开始的时候I：=1，J：=N

   2）以第一个数组元素作为关键数据，赋值给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）/2    

min代表区间中间的结点的位置，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右边的表中。这时low=mid；

    C)如果R[mid].key=a，则查找成功。

   （3）下一次查找针对新的查找区间，重复步骤（1）和（2）

   （4）在查找过程中，low逐步增加，high逐步减少，如果high<low，则查找失败。

实验目的：

本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。

实验内容：

   （1）实现数据序列的输入;

   （2）实现快速排序算法,并对输入的序列排序后输出；

   （3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地

查找,并输出查询结果。

实验器材（设备、元器件）：

      PC机一台，装有C语言集成开发环境。

数据结构与程序：

#include <iostream>

#include <algorithm>

using namespace std;

void quick_sort(int *, int *);

int binary_search(int *, int, int, int);

int main()

{

char ch;

int arr[100] = {1};

int search, pos, count = 0;

while(true)

{

       cin>>ch;

       if(ch == '#')

              break;

       arr[count++] = ch-48;

}

//sort(arr, arr+count);

quick_sort(arr, arr+count);

cout<<"Please input the number you want to search: ";

cin>>search;

pos = binary_search(arr, search, 0, count);

if(pos != -1)

       cout<<"The number "<<search<<" you are searching is in the position of No."<<pos<<endl;

else

       cout<<"The number "<<search<<" you are searching is not in this arrage"<<endl;

return 0;

}

void quick_sort(int *start, int *end)     //快排

{

int *_Start, *_End;

int key = *start;

_Start = start, _End = end-1;

if(_Start > _End);

else

{

       while(_Start < _End)

       {

              while(key < =*_End && _Start < _End) _End--;

              *_Start = *_End;

              while(key > *_Start && _Start < _End) _Start++;

              *_End = *_Start;

       }

       *_Start = key;

       quick_sort(start, _Start);

       quick_sort(_Start+1, end);

}

}

int binary_search(int *arr, int search, int left, int right)  //二分查找

{

if(left > right)

       return -1;

else if(arr[(left+right)/2] == search)

       return (left+right)/2+1;

else if(arr[(left+right)/2] > search)

       return binary_search(arr, search, left, (left+right)/2-1);

else if(arr[(left+right)/2] < search)

       return binary_search(arr, search, (left+right)/2+1, right);

}

程序运行结果：

初始界面：输入待排序数组，并以#结束

自动排序后提示输入需要查找的数据：

查找后结果：（查找数据存在）

（查找数据不存在）

实验结论：

快速排序时间复杂度为O(nlogn)，二分查找时间复杂度为 O(logn)，均为高效算法。

总结及心得体会：

二分查找算法使用前提是查找序列已排序完成。

 

第二篇：排序与查找(综合实验报告)

本科学生实验报告

实验课程名称 数据结构（C语言版） 实验名称 排序与查找 开课学期 2009 至＿ 2010 学年 ＿ 第二 学期

云南师范大学旅游与地理科学学院编印

一、实验准备

二、实验内容、步骤和结果

三、实验小结