查找算法的实现及性能测试与比较

小鱼儿 2021-07-16 16:27 397阅读 0赞

**查找算法的实现及性能测试与比较**

问题描述

在顺序线性表中存放n个整数，n的值由用户输入确定，线性表可以是有序表或无序表。比较各查找算法在不同情况下的时间性能。  
各查找算法的实测时间性能包括两个指标：算法执行的绝对时间和关键字的平均比较次数。  
各查找算法要求评测查找成功与不成功的两种情形。  
为了能比较出各种查找算法执行的绝对时间，需要对表中的数据进行较大量的查找，设为m次，m的值也由用户输入确定。当输入m为1000000时，则对线性表作1000000次查找。  
（1）比较在有序表和无序表中进行顺序查找时，查找成功和查找失败时的算法执行的绝对时间和关键字的平均比较次数。  
（2）比较在同一有序表中进行顺序查找和二分查找时的时间性能。  
（3）比较在同一有序表中进行非递归二分查找和递归二分查找的时间性能。

效果图  
![在这里插入图片描述][20201123214607465.png_pic_center]![在这里插入图片描述][2020112321461374.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][2020112321462916.png_pic_center]  
![在这里插入图片描述][20201123214634150.png_pic_center]

**源码：**

#include<iostream>
    #include<stdlib.h>
    #include<time.h>
    #include<ctime>
    #include<algorithm>
    using namespace std;
    const int Max = 1e7 + 5;
    int lst[Max], lstsort[Max];
    int n;
    double timesequl, timebinary;
    int numsequl, numbinary, fs, fb;
    
    void SequelSearch(int a)
    { 
    	fs = 0;numsequl = 0;timesequl = 0;
    	clock_t begin, end;
    	begin = clock();
    	for (int i = 1;i <= n;i++)
    	{ 
    		numsequl++;
    		if (lst[i] == a)
    		{ 
    			fs = 1;break;
    		}
    	}
    	end = clock();
    	timesequl = end - begin;
    }
    
    void SequelSearchSort(int a)
    { 
    	fs = 0;numsequl = 0;timesequl = 0;
    	clock_t begin, end;
    	begin = clock();
    	for (int i = 1;i <= n;i++)
    	{ 
    		numsequl++;
    		if (lstsort[i] == a)
    		{ 
    			fs = 1;break;
    		}
    	}
    	end = clock();
    	timesequl = end - begin;
    }
    
    void BinearySearch(int a)
    { 
    	fb = 0;numbinary = 0;timebinary = 0;
    	int l = 1, r = n;
    	clock_t begin, end;
    	begin = clock();
    	while (l < r)
    	{ 
    		numbinary++;
    		int mid = (l + r) / 2;
    		if (lst[mid] == a) {  fb = 1;break; }
    		else if (lst[mid] < a)l = mid + 1;
    		else r = mid - 1;
    	}
    	end = clock();
    	timebinary = end - begin;
    }
    
    void IterateBSearch(int a, int l, int r)
    { 
    	if (l > r)return;
    	numbinary++;
    	if (lstsort[(l + r) / 2] == a) {  fb = 1;return; }
    	if (lstsort[(l + r) / 2] < a) IterateBSearch(a, ((l + r) / 2) + 1, r);
    	else IterateBSearch(a, l, (l + r) / 2 - 1);
    }
    
    void project()
    { 
    	cout << "请输入要存放的数字个数：" << endl;
    	cin >> n;
    	cout << "请输入要查找的次数" << endl;
    	int m;cin >> m;
    	for (int i = 1;i <= n;i++)
    	{ 
    		lst[i] = 1 + rand() % 1000000;
    		lstsort[i] = lst[i];
    	}
    	sort(lstsort + 1, lstsort + 1 + n);
    	int f = 1;
    	while (f)
    	{ 
    		system("cls");
    		int sec;
    		cout << "1.比较无序表和顺序表中的顺序查找" << endl;
    		cout << "2.比较在同一有序表中的的顺序查找和二分查找" << endl;
    		cout << "3.比较在同一有序表的非递归二分查找和递归二分查找" << endl;
    		cin >> sec;
    		if (sec == 1)
    		{ 
    			system("cls");
    			int SeNumRight = 0, SeNumFalse = 0, NumRight = 0, NumFalse = 0;
    			double SeRightTime = 0, SeFalseTime = 0, RightTime = 0, FalseTime = 0;
    			for (int i = 1;i <= m;i++)
    			{ 
    				int t = 1 + rand() % 1000000;
    				SequelSearch(t);
    				if (fs) {  RightTime += timesequl;NumRight += numsequl; }
    				else {  FalseTime += timesequl;NumFalse += numsequl; }
    				SequelSearchSort(t);
    				if (fs) {  SeRightTime += timesequl;SeNumRight += numsequl; }
    				else {  SeFalseTime += timesequl;SeNumFalse += numsequl; }
    			}
    			cout << "对于无序表查询m次的信息如下：" << endl << endl;
    			cout << "m次中成功查询的时间为：" << RightTime << endl << endl;
    			cout << "成功查询的平均比较次数为：" << NumRight / m << endl << endl;
    			cout << "m次中失败查询的时间为：" << FalseTime << endl << endl;
    			cout << "失败查询的平均比较次数为：" << NumFalse / m << endl << endl << endl;
    			cout << "对于有序表查询m次的信息如下：" << endl << endl;
    			cout << "m次中成功查询的时间为：" << SeRightTime << endl << endl;
    			cout << "成功查询的平均比较次数为：" << SeNumRight / m << endl << endl;
    			cout << "m次中失败查询的时间为：" << SeFalseTime << endl << endl;
    			cout << "失败查询的平均比较次数为：" << SeNumFalse / m << endl;
    			cout << "时间单位毫秒" << endl;
    		}
    		else if (sec == 2)
    		{ 
    			system("cls");
    			double SeSearchTime = 0, BiSearchTime = 0;
    			for (int i = 1;i <= m;i++)
    			{ 
    				int t = 1 + rand() % 1000000;
    				SequelSearchSort(t);
    				SeSearchTime += timesequl;
    				BinearySearch(t);
    				BiSearchTime += timebinary;
    			}
    			cout << "m次顺序查询的时间为：" << SeSearchTime << endl << endl;
    			cout << "m次二分查询的时间为：" << BiSearchTime << endl << endl;
    			cout << "时间单位毫秒" << endl;
    		}
    		else if (sec == 3)
    		{ 
    			system("cls");
    			double IterateTime = 0, Time = 0;
    			for (int i = 1;i <= m;i++)
    			{ 
    				int t = 1 + rand() % 1000000;
    				BinearySearch(t);
    				Time += timebinary;
    				clock_t b, e;
    				b = clock();
    				IterateBSearch(t, 1, n);
    				e = clock();
    				IterateTime += (e - b);
    			}
    			cout << "m次非迭代查询的时间为：" << Time << endl << endl;
    			cout << "m次迭代查询的时间为：" << IterateTime << endl << endl;
    		}
    		else break;
    		cout << "输入0退出，输入1继续" << endl;
    		cin >> f;
    	}
    }
    
    int main()
    { 
    	srand((unsigned)time(NULL));
    	project();
    	return 0;
    }

[20201123214607465.png_pic_center]: https://img-blog.csdnimg.cn/20201123214607465.png#pic_center
[2020112321461374.png_pic_center]: /images/20210716/93926030b90345cead4b780388ac487c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201123214621450.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2,size_16,color_FFFFFF,t_70#pic_center
[2020112321462916.png_pic_center]: /images/20210716/e7cdf9afc0544369ac900b292f80a1b8.png
[20201123214634150.png_pic_center]: /images/20210716/433033d947704b498282e003f8ee1bdc.png