c/c++语言开发共享数据结构实验4(排序算法的实现及性能分析)

实现了选择排序, 插入排序, 冒泡排序, 快速排序, 改进后的快速排序, 以及两路合并排序.

通过随机函数随机生成100个数, 进行各种排序, 记录排序开始时间以及结束时间, 计算消耗的时间来比较算法的优略.

实现代码:

  #include "iostream"  #include "cstdio"  #include "cstring"  #include "algorithm"  #include "queue"  #include "stack"  #include "cmath"  #include "utility"  #include "map"  #include "set"  #include "vector"  #include "list"  #include "string"  #include "cstdlib"  #include "ctime"  using namespace std;  typedef long long ll;  const int mod = 1e9 + 7;  const int inf = 0x3f3f3f3f;  const int maxn = 1005;  template   void selectsort(t a[], int n)  {  	int small;  	for(int i = 0 ; i < n; ++i) {  		small = i;  		for(int j = i + 1; j < n; ++j)  			if(a[j] < a[small]) small = j;  		swap(a[i], a[small]);  	}  }  template   void insertsort(t a[], int n)  {  	for(int i = 1; i < n; ++i) {  		int j = i;  		t tmp = a[j];  		while(j > 0 && tmp < a[j - 1]) {  			a[j] = a[j - 1];  			j--;  		}  		a[j] = tmp;  	}  }  template   void bubblesort(t a[], int n)  {  	int i = n - 1, j, last;  	while(i > 0) {  		last = 0;  		for(int j = 0; j < i; ++j)  			if(a[j + 1] < a[j]) {  				swap(a[j], a[j + 1]);  				last = j;  			}  		i = last;  	}  }  template   void qsort(t a[], int left, int right)  {  	int i, j;  	if(left < right) {  		i = left, j = right + 1;  		do {  			do i++; while(a[i] < a[left]);  			do j--; while(a[j] > a[left]);  			if(i < j) swap(a[i], a[j]);  		}while(i < j);  		swap(a[left], a[j]);  		qsort(a, left, j - 1);  		qsort(a, j + 1, right);  	}  }  template   void quicksort(t a[], int n)  {  	qsort(a, 0, n - 1);  }  template   void magicqsort(t a[], int left, int right)  {  	int i, j;  	if(right >= 9) {  		if(left < right) {  			i = left, j = right + 1;  			do {  				do i++; while(a[i] < a[left]);  				do j--; while(a[j] > a[left]);  				if(i < j) swap(a[i], a[j]);  			}while(i < j);  			swap(a[left], a[j]);  			magicqsort(a, left, j - 1);  			magicqsort(a, j + 1, right);  		}  	}  	else {  		insertsort(a, right - left + 1);  		return;  	}  }  template   void magicquicksort(t a[], int n)  {  	magicqsort(a, 0, n - 1);  }  template   void merge(t a[], int i1, int j1, int i2, int j2)  {  	t *tmp = new t[j2 - i1 + 1];  	int i = i1, j = i2, k = 0;  	while(i <= j1 && j <= j2) {  		if(a[i] <= a[j]) tmp[k++] = a[i++];  		else tmp[k++] = a[j++];  	}  	while(i <= j1) tmp[k++] = a[i++];  	while(j <= j2) tmp[k++] = a[j++];  	for(int i = 0; i < k; ++i)  		a[i1++] = tmp[i];  	delete []tmp;  }  template   void mergesort(t a[], int n)  {  	int i1, j1, i2, j2, size = 1;  	while(size < 1) {  		i2 = i1 + size;  		j1 = i2 - 1;  		if(i2 + size - 1 > n - 1) j2 = n - 1;  		else j2 = i2 + size - 1;  		merge(a, i1, j1, i2, j2);  		i1 = j2 + 1;  	}  	size *= 2;  }  int main(int argc, char const *argv[])  {  	clock_t start, finish;  	srand(time(null));    	int n = 100, i;  	int *a = new int[n];  	int *b = new int[n];  	int *c = new int[n];  	int *d = new int[n];  	int *e = new int[n];  	int *f = new int[n];  	cout  <<  "待排序序列为:"  <<  endl;  	for(int i = 0; i < n; ++i)  	{  		a[i] = rand()%91;  		cout  <<  a[i]  <<  " ";  		b[i] = a[i];  		c[i] = a[i];  		d[i] = a[i];  		e[i] = a[i];  		f[i] = a[i];  	}  	cout  <<  endl;  	start = clock();	  	selectsort(a, n);  	cout  <<  "经过简单选择排序后的序列为:"  <<  endl;      for(i = 0; i < n; ++i)  		cout  <<  a[i]  <<  " ";  	cout  <<  endl;  	finish = clock();  	cout  <<  "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	start = clock();  	insertsort(b, n);  	cout << "经过直接插入排序后的序列为:" << endl;  	for(i = 0; i < n; ++i)  		cout << b[i] << " ";  	cout << endl;  	finish = clock();  	cout << "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	start = clock();  	bubblesort(c, n);  	cout << "经过冒泡排序后的序列为:" << endl;  	for(i = 0; i < n; ++i)  		cout << c[i] << " ";  	cout << endl;  	finish = clock();  	cout << "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	start = clock();  	quicksort(d, n);  	cout << "经过快速排序后的序列为:" << endl;  	for(i = 0; i < n; i++)  		cout << d[i] << " ";  	cout << endl;  	finish = clock();  	cout << "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	start = clock();  	mergesort(e, n);  	cout << "经过两路合并排序后的序列为:" << endl;  	for(i = 0; i < n; i++)  		cout << e[i] << " ";  	cout << endl;  	finish = clock();  	cout << "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	start = clock();  	magicquicksort(f, n);  	cout << "经过改进后的快速排序后的序列为:" << endl;  	for(i = 0; i < n; ++i)  		cout << f[i] << " ";  	cout << endl;  	finish = clock();  	cout << "开始时间为:" << start << "	" << "结束时间为:" << finish << "   " << "持续时间为:" << (double)(finish - start)/ clocks_per_sec << endl;  	return 0;  }