【深圳大学算法设计与分析】实验一 算法性能分析（十大排序算法）

实验目的

1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理。

2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

实验内容与结果

实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法；

（1）选择排序

原理：从未排序的数据元素中选出最小的一个元素，放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在起始位置，直到未排序元素个数为0。

算法分析：整个算法是双重循环：

外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；

内循环控制每一趟的排序，进行第i趟排序时，所需的比较次数总是n-i次，关键字比较次数KCN 与记录的初始排列无关。

总的关键字比较次数为

记录移动次数RMN与初始排列有关，最好的情况是，排列已经有序，则RMN=0；最坏情况是，每一趟都要进行交换，总的记录移动次数为 RMN = 3(n-1)。

时间复杂度是O(n2)，空间复杂度是O(1）。

选择排序是一种不稳定的排序方法。

（2）冒泡排序

原理：对于n个待排序记录，从第1个记录起，依次比较相邻两个记录的关键字，如果发生逆序，则交换之，直至第n-1个记录和第n个记录比较完，循环n-1次即可排列有序。

算法分析：

最好情况：在记录的初始序列正序时，只执行一趟起泡排序,做n-1次关键字比较，但是不移动记录。

最坏情况：记录的初始序列逆序时，要执行n-1趟冒泡，第i趟做n-i次关键字比较，执行n-i次记录交换，比较次数KCN和交换次数RCN为：

冒泡排序的时间复杂度为O(n2)。

冒泡排序是一种稳定的排序方法。

（3）合并排序

原理：归并是指将两个或两个以上的有序序列合并成一个有序序列。

2-路归并排序：

1. 初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列；
2. 将前后相邻的两个有序序列归并为一个有序序列(两两归并)，得到(int)(n/2)个长度为2或1的有序子序列——一趟归并；
3. 重复做两两归并操作，直到得到长度为n的有序序列为止。

其核心是如何将相邻的两个子序列归并成一个子序列。

算法分析：

（1）假设待归并的两个有序表长度分别为m和n，若是顺序存储，则归并后，都会利用一个长度为m+n的数组作为辅助数组用于保存合并序列，则空间复杂度为O（m+n）

（2）归并操作至多只需要m+n次移位和m+n次比较，因此归并的时间复杂度为O(m+n)

（3）如果待排序的记录为n个，则需要做(int)(log2n)趟2－路归并排序，每趟2－路归并排序的时间复杂度为O(n),因此2－路归并排序的时间复杂度为O(nlog n)。

（4）需要额外空间，大小与待排序记录空间相同，则空间复杂度为O(n)。

（5）归并排序是一种稳定的排序方法。

（4）快速排序

原理：任取待排序记录序列中的某个记录作为枢轴(也称为基准、锚点或支点记录，pivot), 通过一趟排序，将待排序记录以枢轴为界分割成两部分，其中，比枢轴关键字小的记录都在枢轴的前面，而枢轴后面的记录都比枢轴关键字大。然后，采用同样方法再分别对这两部分子序列进行排序，最后达到整个序列有序。

算法分析：时间复杂度是O(nlog n)，空间复杂度是：S(n)=O(㏒n)。

快速排序是一种不稳定的排序方法。

（5）插入排序

原理：将待排序的记录依次插入到已排好序的序列中，得到一个新的、记录数增加1的有序表。 直到所有的记录都插入完为止。

算法分析：

关键字比较次数和记录移动次数与记录的初始排列有关。

时间复杂度为O(n2)，空间复杂度为O(1)。

最大的优点是简单，在记录数较少时，是比较好的办法。

插入排序是一种稳定的排序方法。

当n=10000时

当n=20000时

当n=30000时

当n=40000时

当n=50000时

表格如下

图像如下

在大数据量进行排序时，冒泡排序需要耗费大量时间，选择排序和插入排序所耗费时间略少，合并排序和快速排序耗费时间最少。

（6）选择排序

在大数据量排序情况下，理论值大于实际值不少，原因是基准值n=10000时平均运行时间较长。

（7）冒泡排序

在大数据量排序情况下，理论值和实际值较为相似；理论值略小于实际值的原因是基准值n=10000时平均运行时间较少。

（8）合并排序

在大数据量排序情况下，理论值和实际值较为接近。

（9）快速排序

在大数据量排序情况下，理论值和实际值较为相似，且快速排序的平均运行时间少，效率高。

（10）插入排序

在大数据量排序情况下，理论值和实际值几乎一致。

从10亿数据中快速挑选出最大的10个数。

算法思想：将十亿分块，每个块为十万，用选择排序将每个块最大的十个数进入队列，最后再统一取出找出最大的十个数即为最终所求。

最终结果

实验总结

综合上述实验可得，当数据规模相当大时，选择排序、冒泡排序、插入排序耗费的时间相当多，该类算法虽然简单易懂，但是效率较低，不适合处理大量数据。合并排序和快速排序采用了分治、递归的思想，运行大量数据时效率仍然非常高，远胜于前面的几种排序算法。因此，当数据规模较大时，选择后面两种排序算法为佳。

实验代码

#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
 
int n;	//数据总数
int* zu;
queue<int> q;
 
int select()//选择排序
{
	int qi, zhi;	//记录起止时间
	qi = clock();
 
	//
	for (int i = 0; i < n; i++)
	{
		int min = 99999,minpos;
 
		for (int j = i; j < n; j++)
			if (zu[j] < min)//找到最小值放到前面
			{
				min = zu[j];
				minpos = j;
			}
 
		if (i != minpos)
			swap(zu[i], zu[minpos]);//交换
	}
	//
 
	zhi = clock();
	return zhi - qi;	//返回时间差
}
 
int bubble()//冒泡排序
{
	int qi, zhi;	//记录起止时间
	qi = clock();
 
	//
	int i, j;
	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n-i-1; j++)
			if (zu[j] > zu[j + 1])
				swap(zu[j], zu[j + 1]);
	//
 
	zhi = clock();
	return zhi - qi;	//返回时间差
}
 
void merge(int* a, int l, int mid, int r)//合并两序列
{
	int* b = new int[r - l + 1];
	int i = l, j = mid + 1, k = 0;
 
	while (i <= mid && j <= r)
	{
		if (a[i] <= a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}
	while (i <= mid)
		b[k++] = a[i++];
	while (j <= r)
		b[k++] = a[j++];
 
	for (i = l,k=0; i <= r; i++)//将排序好的序列传回去
		a[i] = b[k++];
}
 
void mergesort(int *a,int l,int r)//递归进行归并排序
{
	if (l < r)
	{
		int mid = (l + r) / 2;
		mergesort(a, l, mid);
		mergesort(a, mid + 1, r);
		merge(a, l, mid, r);
	}
}
 
int guibing()//归并排序
{
	int qi, zhi;	//记录起止时间
	qi = clock();
 
	//
		mergesort(zu, 0, n - 1);
	//
 
	zhi = clock();
	return zhi - qi;	//返回时间差
}
 
int part(int l,int r)//划分子表并返回轴的位置
{
	int zhou = zu[l];//保存轴的值
	while (l < r)
	{
		while (l < r && zhou <= zu[r])//注意'='不能漏掉
			r--;
		zu[l] = zu[r];
 
		while (l < r && zhou >= zu[l])
			l++;
		zu[r] = zu[l];
	}//	循环结束的条件是l==r
 
	zu[l] = zhou;//将轴的值放入l==r的位置
	return l;	//返回轴的位置
}
 
void qsort(int l, int r)
{
	int zhoupos;
	if (l < r)
	{
		zhoupos = part(l, r);
		qsort(l, zhoupos - 1);
		qsort(zhoupos + 1, r);
	}
}
 
int quick()//快速排序
{
	int qi, zhi;	//记录起止时间
	qi = clock();
 
	//
	qsort(0, n - 1);
	//
 
	zhi = clock();
	return zhi - qi;	//返回时间差
}
 
int insert()//插入排序
{
	int qi, zhi;	//记录起止时间
	qi = clock();
 
	//
	int i, j;
	for (i = 1; i < n; i++)//第一个数据不用插入
	{
		int temp = zu[i];
		for (j = i; j > 0; j--)
		{
			if (temp < zu[j - 1])
				zu[j] = zu[j - 1];
			else
				break;
		}
		zu[j] = temp;
	}	
	//
 
	zhi = clock();
	return zhi - qi;	//返回时间差
}
 
void show()//输出函数
{
	for (int i = 0; i < n; i++)
	{
		cout << zu[i] << " ";
	}
	cout << endl;
}
 
void ceshi(int ci, int size)//测试次数和排序数组大小
{
	n = size;
	zu=new int[size];//动态建立数组
	srand(time(0));
	int t1,t2,t3,t4,t5, i, j;
	t1 = t2 = t3 = t4 = t5 = 0;
 
	/*
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		//show();//1
		t1+= select();
		t2 += bubble();
		t3 += guibing();		不能放一起，要分开！！！！！
		t4 += quick();
		t5 += insert();		
		//show(); cout << endl;//2	语句1和2用来测试排序算法是否正确，此时n要取小值
	}
	*/
 
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		t1 += select();
	}
 
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		t2 += bubble();
	}
 
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		t3 += guibing();
	}
 
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		t4 += quick();
	}
 
	for (i = 0; i < ci; i++)
	{
		for (j = 0; j < size; j++)
			zu[j] = rand();
		t5 += insert();
	}
 
	cout << "选择排序的平均运行时间为" << t1 / ci << "ms" << endl;
	cout << "冒泡排序的平均运行时间为" << t2 / ci << "ms" << endl;
	cout << "合并排序的平均运行时间为" << t3 / ci << "ms" << endl;
	cout << "快速排序的平均运行时间为" << t4 / ci << "ms" << endl;
	cout << "插入排序的平均运行时间为" << t5 / ci << "ms" << endl;
}
 
void selectshiyi()//选择排序从10亿中找最大的10个
{
	int i,j,k,l;
	srand(time(0));
	zu = new int[100000];
	k = 0;
	n = 100000;
	for (i = 0; i < 1000000000; i++)//将十亿分块，每个块为十万，将每个块最大的十个数进入队列，最后再统一取出找出最大的十个数
	{
		zu[k++] = rand();
		if (k == 99999) //每次数组存满十万则进行操作
		{
			for (l = 0; l < 10; l++)
			{
				int max = -1, maxpos;
 
				for (j = 0; j < n; j++)
					if (zu[j] > max)//找到最大值
					{
						max = zu[j];
						maxpos = j;
					}
				q.push(zu[maxpos]);//进入队列
				zu[maxpos] = 0;
			}
			k = 0;
		}
	}
 
	n = 10000;
	for (i = 0; i < n; i++)//取出队列中的值
	{
		zu[i] = q.front();
		q.pop();
	}
	
	for (l = 0; l < 10; l++)//将最大的十个数存入队列
	{
		int max = -1, maxpos;
 
		for (j = 0; j < n; j++)
			if (zu[j] > max)
			{
				max = zu[j];
				maxpos = j;
			}
		q.push(zu[maxpos]);
		zu[maxpos] = 0;
	}
 
	for (i = 0; i < 10; i++)//输出
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
}
 
int main()
{	
	/*
	for (int i = 1; i <= 5; i++)
	{
		cout << endl << endl;
		int size = i*10000;	//设置数组大小
		cout << "排序数组大小n=" << size << endl;
		ceshi(20, size);	//测试20次
	}
	*/
	selectshiyi();
}

（by 归忆）