数据结构实验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;
}