1009040130-贺程-实验2 (2)

printf(\没有找到%d\\n\ else printf(\是第%d个数\\n\

printf(\程序运行时间：%f\\n\}

程序执行结果：800是56969个数 程序运行时间是：0.160

再从同样的文件中运用二分查找，查找相同的数据。

2． 二分查找 归并分类 快速分类

在查找前先运用二路归并分类 或 快速分类 对待查找数据进行排序。

#include #include #define N 1000 #define len 100000

FILE *f1,*f2,*f3;

int search_bin(int key,int n[]){ int high = len-1,low = 0,middle;

while(low <= high){ middle = (low+high)/2; if(key < n[middle]) high = middle-1; else if(key > n[middle]) low = middle+1; else return middle; }

return 0; }

void Merge(int temp[],int result[],int size){

//对序列r[0]一r[n-1]进行一次二路归并排序，每个有序子(文件)序列的长度为size

int i,j,lb1,ub1,lb2,ub2,sp; lb1=0; //第一个子文件(序列)的起始位置 sp =0;

while(lb1+size<=len-1) //测试是否存在两个可以合并的子文件 { lb2=lb1+size; //第二个子文件(序列)的起始位置 ub1=lb2-1; //第一个子文件(序列)的结束位置 if (lb2+size-1<= len-1) //设置第二个子序列的结束位置 ub2=lb2+size -1; else ub2=len-1; for(i=lb1,j=lb2; i<=ub1 && j<=ub2;) //合并两个子文件 if(temp[i]<=temp[j]) result[sp++]=temp[i++]; else result[sp++]=temp[j++]; while(i<=ub1) //序列2已归并完,将序列1中剩余的记录顺序存放到数组swap中 result[sp++]=temp[i++]; while(j<=ub2) //序列1已归并完,将序列2中剩余的记录顺序存放到数组swap中 result[sp++]=temp[j++]; lb1=ub2+1; }//while

for (i=lb1; i

void Merge_Sort(int n[]){ //对数组n归并 int size = 1,result[len]; //子文件的大小 while (size < len) { Merge(n,result,size); //从a归并到b size*=2; Merge (result,n,size); //从b归并到a size*=2; } }

int Partition(int n[],int low,int high){ int pivotkey; n[0] = n[low]; pivotkey = n[low]; while(low < high){ while(low < high && n[high] >= pivotkey) high--; n[low] = n[high]; while(low < high && n[low] <= pivotkey) low++; n[high] = n[low]; }

n[low] = n[0]; return low; }

void QSort(int n[],int low,int high){ int pivotloc; if(low < high){ pivotloc = Partition(n,low,high); //将n[low...high]一分为二 QSort(n,low,pivotloc-1); //对低子表递归排序，pivotloc是枢轴位置 QSort(n,pivotloc+1,high); //对高子表递归排序 } }

void Quick_Sort(int n[]){ QSort(n,0,len-1); }

void main(){

int key,i=0,j,data,n[len],t1,t2,t3,t4,t5,t6; f1 = fopen(\//读操作 f2 = fopen(\ fscanf(f1,\

while(i < len){ //这里用数组存放文件中的数据，占用了额外的存储空间，但是可以方便对不同算法进行时间复杂度分析 fscanf(f2,\ n[i++] = data; }

//归并排序 和 快速排序选择运行其一 t1 = clock(); Merge_Sort(n);

t2 = clock(); /*

t3 = clock(); Quick_Sort(n); t4 = clock(); */

f3 = fopen( \//写操作,把排好序的数字写到文件sortResult.txt中 for(j = 0;j < len;j++){ fprintf(f3,\ fprintf(f3,\ }

fclose(f1); fclose(f2); fclose(f3);

t5 = clock();

for(j = 0;j < N;j++) i = search_bin(key,n); t6 = clock();

if(i == -1) printf(\没有找到%d\\n\ else printf(\是第%d个数\\n\

printf(\归并排序时间：%f\\n\ printf(\快速排序时间：%f\\n\ printf(\二分查找时间：%f\\n\}

归并排序结果：

快速排序结果：

由多次测试时间可以看出，排好序后，二分查找效率相当高，尽管基数是100000，无论从中查找那个关键字，都能迅速完成，经分析二分查找的时间复杂度为O(log2n)，而且在基数为100000的条件下测试运行归并分类 和 快速分类 的运行时间是差不多的，对着100000个数据排序时间均为 25ms左右即可完成。

实验结果及其分析

由于要采用读写文件对测试数据进行操作，在对统计不同基数和关键字下进行查找和排序带来不便，而且在基数相差不是很大的情况下，计算机处理归并分类和快速分类的时间差异效果并不明显，所以本次试验并未对不同数据进行时间统计。但是可以明显看到二分查找交顺序查找有更好的效率。

通过本次试验，更好的掌握了查找和排序经典算法的思路和转化为程序运行，体现的良好效果。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新经管营销1009040130-贺程-实验2 (2)全文阅读和word下载服务。