排序算法的实现及性能测试及比较

刺骨的言语ヽ痛彻心扉 2021-07-17 00:47 366阅读 0赞

在书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过具体数据比较各种算法的关键字比较次数和记录移动次数，以取得直观感受。  
要求：  
（1）编写程序创建一些整数文件用于排序。创建的这些文件可以根据需要生成不同的长度，如长度分别为20，200和2000，以正序、逆序、随机顺序的方式创建这些文件，通过把所有这些测试数据保存在文件中（而不是每次在测试程序时用随机数生成），可以使用同样的数据去测试不同的方法，因此会更易于比较这些方法的性能。  
（2）数据表采用顺序存储结构，实现插入排序，选择排序，希尔排序，归并排序，快速排序，堆排序等排序，并对这些算法的实现效率进行比较和分析。  
（3）排序的指标包含：运行时间，比较次数，移动次数。

//suda的同窗请勿直接copy，可参考。

源码：

#include<iostream>
    #include<string>
    #include<map>
    #include<algorithm>
    #include<memory.h>
    #include<cmath>
    #include<ctime>
    #define pii pair<int,int>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 2e4 + 5;
    int Mod = 1e9 + 7;
    
    class mysort
    { 
    public:
    	mysort() { };
    	void sec_sort(int n,int* s);
    	void insert_sort(int n, int* s);
    	void merge(int f1, int l1, int l2,int* a);
    	void merge_sort(int f, int l,int* a);
    	void shell_sort(int n, int* a);
    	void sift(int k, int l, int* lst);
    	void heap_sort(int n,int* a);
    	int part(int l, int r, int* lst);
    	void quick_sort(int f, int l, int* a);
    	void init();
    	int* get_data(int n) {  return data[n]; }
    private:
    	int data[4][20005];//1为正序 2逆序 3随机
    };
    
    int lst[20005], count1 = 0, count2 = 0;
    void fz(int n, int* a, int* b)
    { 
    	for (int i = 1;i <= n;i++)b[i] = a[i]; 
    	count1 = 0, count2 = 0;
    }
    
    
    void mysort::sift(int k, int l, int* lst)
    { 
    	int i, j, t;
    	i = k;j = 2 * i ;
    	while (j <= l)
    	{ 
    		count1 += 2;
    		if (j < l && lst[j + 1] > lst[j])j++;
    		if (lst[i] > lst[j])break;
    		else
    		{ 
    			t = lst[i], lst[i] = lst[j], lst[j] = t;
    			i = j;j = i * 2 ;count2++;
    		}
    	}
    }
    
    void mysort::heap_sort(int n, int* lst)
    { 
    	int i, t;
    	for (int i = n / 2;i >= 1;i--)sift(i, n,lst);
    	for (int i = 1;i <= n;i++)
    	{ 
    		t = lst[1];lst[1] = lst[n - i + 1];lst[n - i + 1] = t;count2++;
    		sift(1, n - i,lst);
    	}
    }
    
    void mysort::quick_sort(int f, int l, int* a)
    { 
    	if (f >= l) return;
    	else
    	{ 
    		int p = part(f, l, a);
    		quick_sort(f, p - 1, a);
    		quick_sort(p + 1, l, a);
    	}
    }
    
    int mysort::part(int f, int l, int* lst)
    { 
    	int i = f, j = l, t;
    	while (i < j)
    	{ 
    		count1 += 2;
    		while (lst[i] <= lst[j] && i < j) {  j--;count1++;}
    		if (i < j)
    		{ 
    			t = lst[i], lst[i] = lst[j], lst[i] = t;i++;
    			count2++;
    		}
    		while (lst[i] <= lst[j] && i < j) { i++;count1++;}
    		if (i < j)
    		{ 
    			t = lst[i], lst[i] = lst[j], lst[j] = t;j--;
    			count2++;
    		}
    	}
    	return i;
    }
    
    void mysort::shell_sort(int n, int* a)
    { 
    	fz(20000, a, lst);
    	int d, i, j, t, count1 = 0, count2 = 0;
    	clock_t b, f;
    	b = clock();
    	for (d = n / 2;d >= 1;d = d / 2)
    	{ 
    		for (i = d;i <= n;i++)
    		{ 
    			t = lst[i];count1++;
    			for (j = i - d;j >= 1 && t < lst[j];j -= d)
    			{ 
    				lst[j + d] = lst[j];count1++;count2++;
    			}
    			lst[j + d] = t;count2++;
    		}
    	}
    	f = clock();
    	cout <<"比较次数：" << count1
    		<< endl << "移动次数：" << count2 << "耗时：" << f - b << endl;
    }
    
    void mysort::merge_sort(int f, int l,int* a)
    { 
    	if (f == l)return;
    	else
    	{ 
    		int mid = (f + l) / 2;
    		merge_sort(f, mid,a);
    		merge_sort(mid + 1, l,a);
    		merge(f, mid, l,a);
    	}
    }
    int t[20005];
    void mysort::merge(int f1, int l1, int l2,int* a)
    { 
    	int i = f1, j = l1 + 1, k = f1;
    	while (i <= l1 && j <= l2)
    	{ 
    		count1++;count2++;
    		if (a[i] <= a[j])t[k++] = a[i++];
    		else t[k++] = a[j++];
    	}
    	while (i <= l1) {  t[k++] = a[i++];count2++; }
    	while (j <= l2) {  t[k++] = a[j++];count2++; }
    	for (int i = f1;i <= l2;i++)
    	{ 
    		a[i] = t[i];count2++;
    	}
    }
    
    void mysort::init()
    { 
    	for (int i = 1;i <= 20005;i++)
    	{ 
    		int q=1 + rand() % 20000;
    		data[3][i] = q; data[1][i] = q; data[2][i] = q;
    	}
    	sort(data[1] + 1, data[1] + 20000);
    	sort(data[2] + 1, data[2] + 20000, greater<int>());
    }
    
    
    
    void mysort::sec_sort(int n,int* a)
    { 
    	fz(n, a, lst);
    	int d = 0,count1 = 0, count2 = 0;
    	ll count = 0;
    	clock_t b, f;
    	b = clock();
    	for (int i = 1;i <= n;i++)
    	{ 
    		d = i;
    		for (int j = i+1;j <= n;j++)
    		{ 
    			if (lst[d] < lst[j])d = j;
    			count1++;
    		}
    		int t = lst[i];lst[i] = lst[d];lst[d] = t;
    		count2 += 1;
    	}
    	f = clock();
    	cout  << "比较次数：" << count1
    		<< endl << "移动次数：" << count2 << "耗时：" << f - b << endl;
    }
    
    void mysort::insert_sort(int n, int* a)
    { 
    	fz(n, a, lst);
    	int j, t, count1 = 0, count2 = 0;
    	ll count = 0;
    	clock_t b, f;
    	b = clock();
    	for (int i = 2;i <= n;i++)
    	{ 
    		t = lst[i];
    		count1 += 2;
    		for (j = i - 1;j >= 1 && t < lst[j];j--) {  lst[j + 1] = lst[j]; count1++;count2++; }
    		if (t != lst[j+1]) {  lst[j + 1] = t;count2++; }
    	}
    	f = clock();
    	cout  << "比较次数：" << count1
    		<< endl << "移动次数：" << count2 << "耗时：" << f - b << endl;
    }
    
    mysort s;
    clock_t b, f;
    void xinit(int n)
    { 
    	count1 = 0;count2 = 0;
    }
    void out()
    { 
    	cout << "比较次数：" << count1
    		<< endl << "移动次数：" << count2 << "耗时：" << f - b << endl << endl;
    }
    void project()
    { 
    	s.init();
    	int n=1;
    	while(n)
    	{ 
    		system("cls");
    		cout << "输入想要对多少个元素排序（超过3500在极端条件下快排会迭代过多爆栈区，退出程序,但为了比较更大数据n最多不超过2W）" << endl;
    		cin >> n;
    		system("cls");
    		cout << "插入排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		s.insert_sort(n, s.get_data(1));
    		cout <<endl<< "无序表结果：" << endl;
    		s.insert_sort(n, s.get_data(2));
    		cout << endl << "乱序表结果：" << endl;
    		s.insert_sort(n, s.get_data(3));
    		cout << endl;
    
    		cout << "选择排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		s.sec_sort(n, s.get_data(1));
    		cout <<endl<< "无序表结果：" << endl;
    		s.sec_sort(n, s.get_data(2));
    		cout <<endl<< "乱序表结果：" << endl;
    		s.sec_sort(n, s.get_data(3));
    		cout << endl;
    
    		cout << "希尔排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		s.shell_sort(n, s.get_data(1));
    		cout <<endl<< "无序表结果：" << endl;
    		s.shell_sort(n, s.get_data(2));
    		cout <<endl<< "乱序表结果：" << endl;
    		s.shell_sort(n, s.get_data(3));
    		cout << endl;
    
    		cout << "归并排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		fz(n, s.get_data(1), lst);b = clock();
    		s.merge_sort(1,n,lst);
    		f = clock();out();
    		cout << "无序表结果：" << endl;
    		fz(n, s.get_data(2), lst);b = clock();
    		s.merge_sort(1, n, lst);
    		f = clock();out();
    		cout << "乱序表结果：" << endl;
    		fz(n, s.get_data(3), lst);b = clock();
    		s.merge_sort(1, n, lst);
    		f = clock();out();
    		cout << endl;
    
    		cout << "堆排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		fz(n, s.get_data(1), lst);b = clock();
    		s.heap_sort(n, lst);
    		f = clock();out();
    		cout << "无序表结果：" << endl;
    		fz(n, s.get_data(2), lst);b = clock();
    		s.heap_sort(n, lst);
    		f = clock();out();
    		cout << "乱序表结果：" << endl;
    		fz(n, s.get_data(3), lst);b = clock();
    		s.heap_sort(n, lst);
    		f = clock();out();
    		cout << endl;
    
    		cout << "快速排序结果如下" << endl << endl;
    		cout << "有序表结果：" << endl;
    		fz(n, s.get_data(1), lst);b = clock();
    		s.quick_sort(1, n, lst);
    		f = clock();out();
    		cout << "无序表结果：" << endl;
    		fz(n, s.get_data(2), lst);b = clock();
    		s.quick_sort(1, n, lst);
    		f = clock();out();
    		cout << "乱序表结果：" << endl;
    		fz(n, s.get_data(3), lst);b = clock();
    		s.quick_sort(1, n, lst);
    		f = clock();out();
    		cout << endl;
    		cout << "如果想退出，输入0否则输入1" << endl;
    		cin >> n;
    	}
    }
    
    int main()
    { 
    	project();
    	return 0;
    }

这估计是今年最后一篇博文了，借此机会来总结记录一下今年的学习与生活。

在上半年的家里蹲过程中，可以说还是很惬意和开心的。学习上：周一至周五把该上的网课上了，然后课余时间提前把数据结构学了一遍，配合着数据结构的书把大一寒假看的啊哈算法复习了，在网络攻防上也学习了更多基于kali的攻击方法。在网易云课堂上报了声乐课，以前连气泡音、唇颤音怎么发都不知道，学习这方面还是挺有意思的。去新华书店将之前学的催眠复习了一遍，但是练习的机会不多没感觉有什么进步。生活上：晚上和好友一起跑步，一起交流生活和学习中的问题（朋友选学计算机，非常强）。在周末我们6个好朋友抽一天早上买食材，中午BBQ，晚上一起LOL开黑，或者是一起去骑行、爬山。现在回想起来感觉那些日子好爽。

到了暑假及下半年，当时抱着去acm集训队学习算法的氛围浓厚好去学习一段时间。结果现在上了车组好了队，开始了acmer生涯。同时也很幸运地遇到了两个有趣且优秀的队友，感谢slf、szb这半年的陪伴与帮助，让这平淡大学生活多出了不少乐趣。这下半年，主要都学习算法去了，毕竟感觉自己本身基础很差，要多加训练才行，希望接下来的ICPC济南站和太极杯能顺利吧。不知不觉又到了一点，该回寝了，不过想到明天无早八，估计室友还在打元神，正好回去泡杯牛奶，睡觉。最后要说这一年有什么遗憾的话，估计是没找到npy…汰