查找与排序实验报告

实 验 报 告

实验原理：

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

假设要排序的数组是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

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

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

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

实验目的：

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

实验内容：

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

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

第1页

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

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

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

数据结构与程序：

#include #include

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) { }

//sort(arr, arr+count); quick_sort(arr, arr+count);

cout<<\ cin>>search;

pos = binary_search(arr, search, 0, count); if(pos != -1)

cout<<\number \you are searching is in the position of

第2页

cin>>ch; if(ch == '#')

break;

arr[count++] = ch-48;

No.\ else

cout<<\number \you are searching is not in this

arrage\ return 0; }

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

int *_Start, *_End; int key = *start;

_Start = start, _End = end-1; if(_Start > _End); else { } }

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

if(left > right)

return -1;

第3页

while(_Start < _End) { }

*_Start = key;

quick_sort(start, _Start); quick_sort(_Start+1, end);

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

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

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

}

return (left+right)/2+1;

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

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

程序运行结果：

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

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

第4页

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

（查找数据不存在）

第5页

实验结论：

快速排序时间复杂度为O(nlogn)，二分查找时间复杂度为

O(logn)，均为高效算法。

总结及心得体会：

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

第6页

本文来源：https://www.bwwdw.com/article/ewth.html