实 验 报 告
实验原理:
快速排序的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
假设要排序的数组是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 学年 _ 第二 学期
云南师范大学旅游与地理科学学院编印
一、实验准备
二、实验内容、步骤和结果
三、实验小结
实验十查找排序计算机学院12级2班1211020xx李龙实验目的1掌握折半查找算法的思想2实现折半查找的算法3掌握常见的排序算法插…
实验五查找与排序实验课程名数据结构与算法专业班级12级软件工程1班学号20xx40450149姓名刘浩实验时间61462134节实…
电子科技大学信息与软件工程学院实验报告电子科技大学实验报告课程名称学生姓名学号点名序号指导教师实验地点实验时间20xx20xx2学…
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
信息检索课程结业报告姓学信息检索与web搜索应用背景及概念信息检索InformationRetrieval是指信息按一定的方式组织…
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
学生成绩查询系统一实习任务2二系统分析3三系统设计4四调试排错测试试运行过程7五源程序完整或主要代码10六总结与体会17七参考文献…
附件2天津商业大学学生实验报告开课实验室403机房开课时间20xx年10月17日实验报告20xx年10月17日注1每个实验项目一份…