设计3题目：各种排序算法及性能分析

1、设计3目的

掌握各种内排序算法设计及其执行绝对时间，并对其时间性能进行比较。

2、设计3正文

2.1 实验内容

内容：编写一个程序，随机产生n个1-99的正整数序列，分别采用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序和二路归并排序算法对其递增排序，求出每种排序方法所需要的绝对时间。

要求：为了便于体现各类排序算法的执行时间差别，要求产生不少于50000个随机数进行测试，同时需要编写测试函数用于测试排序结果是否为递增的。

2.2 实验分析

2-1各种排序算法及性能分析功能图

本次的程序是一个对各种算法进行统计的集合，需要编写各种排序算法，在程序中需要有生成随机数的initial（）函数、进行位置交换的函数swap（）以及验证其正确性的test（）函数、对数据及堆排序数据复制的copy（）以及copy1（）函数。而最为关键的则是实验中涉及算法的函数，包括了InsertSort（）、BinInsertSort（）、 ShellSort（）、BubbleSort（）、GBubbleSort（）、partition（）、QuickSort（）、SelectSort（）、sift（）、HeapSort（）、Merge（）、MergePass（）和MergeSort（）函数的编写，在每种排序后有对应的计算时间所用函数，该程序的效果如图2-1各种排序算法及性能分析功能图所示。

在这些排序算法中性能最好的两种为堆排序和二路归并排序，其中堆排序是通过将无序表转化为堆，可以直接找到表中最大值或者最小值，然后将其提取出来，令剩余的记录再重建一个堆，取出次大值或者次小值，如此反复执行就可以得到一个有序序列。二路归并排序是分为两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。在归并的过程中将子表两两合并，每合并一次，就会产生一个新的且更长的有序表，重复这一步骤，直到最后只剩下一个子表，这个子表就是排好序的线性表。

堆排序通过循环对堆的元素进行排列来构造大根堆或是小根堆，该过程如图2-3所示

2-3大根堆的构建

堆排序通过两个函数HeapSort（）和sift（）来实现排序的功能，其中HeapSort（）通过循环调用sift（）来实现大根堆的构建和最大元素的交换。Sift（）函数会通过比较孩子和双亲的大小来构建大根堆，并且会向下继续判断来保证后面的孩子不会被破坏大根堆的结构。

2-4二路归并排序过程

二路归并排序通过Merge（）、MergePass（）和MergeSort（）三个函数来实现，其中MergeSort（）函数循环调用MergePass（）函数，然后MergePass（）函数在循环调用Merge（）函数来实现划分和合并的操作。其中对数组的具体操作过程如图2-4所示，先将数组划分为单个元素，然后再两两合并。

2.3 实验结果与测试

?2-3运行结果

对于运行结果进行来看，冒泡排序用时最长，改进冒泡排序相对于冒泡排序来说性能有很大的提升，堆排序用时最短。堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O (nlogn)）而除了高效之外，还只需要O (1)的辅助空间，既最高效率又最节省空间。

3、设计3总结

对于这次实验我写了直接插入排序、折半插入排序、希尔排序、冒泡排序、改进冒泡排序、快速排序、简单选择排序、堆排序和二路归并排序算法。在这么多排序算法里面我所熟知的只有冒泡排序这一个，并且我发现冒泡排序的性能要远远落后于其他排序算法。并且其中快速排序，堆排序，二路归并排序，都用到了递归的操作，并且递归算法我并不是很熟悉。这也导致了我对这些排序算法很难理解，但最终结果是好的，我学会了更多新的排序算法，还意识到算法的性能和效率对于编程的重要性，也明白了我的代码能力还很薄弱。

这些新颖的排序算法极大的开阔了我的思路，也为我以后的代码提供了更多的选择。在比较各种排序算法时，我注意到了时间复杂度和空间复杂度的重要性。不同的算法在这些方面有着显著差异，这直接影响着它们的实际应用场景。例如，快速排序和堆排序虽然在某些情况下比冒泡排序快得多，但它们的空间复杂度较高，可能会对资源有限的系统造成压力。对于一些简单的排序算法，如冒泡排序，时间复杂度为O(n^2)，意味着随着数据规模的增加，算法的运行时间会急剧增长。而快速排序和堆排序的时间复杂度为O(nlogn)，在许多情况下性能更优。

此外，我也意识到了算法的可读性和可维护性。虽然一些算法在性能上可能更优秀，但如果它们的代码难以理解和维护，那么在长期的项目开发中可能会带来问题。因此，在选择排序算法时，需要综合考虑多个因素。

?

4、代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MaxSize 50001

void swap(int &x,int &y)//交换
{
	int tmp=x;
	x=y;
	y=tmp;
}
void initial(int R[],int low,int high)//初始化产生50001个随机数
{
	int i;
	srand((unsigned)time(NULL));
	for(i=low;i<high;i++)
	{
		R[i]=rand()%99+1;
	}
}
void copy(int R[],int R1[],int n)//用于从0开始排序
{
	for(int i=0;i<n;i++)
	  R1[i]=R[i];
}
void copy1(int R[],int R1[],int n)//用于从1开始的排序
{
	for(int i=1;i<n;i++)
	  R1[i]=R[i];
}

void test(int R[],int low,int high)//用于检验排序是否正确
{
	for(int i=low;i<high-1;i++)
	{
		if(R[i]>R[i+1]){
          printf("\t      错误\n");
		  return ;
		}
	}
    printf("\t      正确\n");
}

void InsertSort(int R[],int n)//直接插入排序
{
	int i,j;
	int tmp;
	for(i=1;i<n;i++)
	{
		if(R[i]<R[i-1])//反序时
		{
			tmp=R[i];
			j=i-1;
			do{
				R[j+1]=R[j];//关键字大于R[1]的记录后移
				j--;
			}while(j>=0&&R[j]>tmp);
			R[j+1]=tmp;
		}
	}
}

void BinInsertSort(int R[],int n)//折半插入排序，无序区中元素插到有序区里
{
	int i,j,low,high,mid;
	int tmp;
	for(i=1;i<n;i++)
	{
		if(R[i]<R[i-1])
		{
			tmp=R[i];
			low=0;high=i-1;
			while(low<=high)
			{
				mid=(low+high)/2;
				if(tmp<R[mid])
				  high=mid-1;
				else
				  low=mid+1;
			}
			for(j=i-1;j>=high+1;j--)//元素后移
			  R[j+1]=R[j];
			R[high+1]=tmp;
		}
	}
}

void ShellSort(int R[],int n)//希尔排序，每间隔d相比较，反序时交换顺序
{
	int i,j,d;
	int tmp;
	d=n/2;
	while(d>0)
	{
		for(i=d;i<n;i++)
		{
			tmp=R[i];
			j=i-d;
			while(j>=0&&tmp<R[j])
			{
				R[j+d]=R[j];
				j=j-d;
			}
			R[j+d]=tmp;
		}
		d=d/2;
	}
}

void BubbleSort(int R[],int n)//冒泡排序
{
	int i,j;
	for(i=0;i<n-1;i++)
	{
	    for(j=n-1;j>i;j--)
	    {
	    	if(R[j]<R[j-1])
		    {
			  swap(R[j],R[j-1]);
		    }
		}
	}
}

void GBubbleSort(int R[],int n)//改进冒泡排序
{
	int i,j;
	bool exchange;
	for(i=0;i<n-1;i++)
	{
		exchange=false;
	    for(j=n-1;j>i;j--)
	    {
	    	if(R[j]<R[j-1])
		    {
			  swap(R[j],R[j-1]);
			  exchange=true;
		    }
		}
		if( !exchange)
		{
			return;
		}
	}
}

int partition(int R[],int s,int t)
{
	int i=s,j=t;
	int tmp=R[i];
	while(i<j)
	{
		while(j>i&&R[j]>=tmp)
		  j--;  //从右往左扫描，找一个小于tmp的
		R[i]=R[j];//找到的R[j]放到R[i]处
		while(i<j&&R[i]<=tmp)
		  i++;//从左往右扫描，找到个大于tmp的
		R[j]=R[i];//找到的R[i]放到 R[j]处
	}
	R[i]=tmp;
	return i;
}

void QuickSort(int R[],int s,int t)//快速排序,交替所有关键字比基准小的放到前一部分 ， 比基准大的放到后一部分
{
	int i;
	if(s<t)
	{
		i=partition(R,s,t);
		QuickSort(R,s,i-1);
		QuickSort(R,i+1,t);
	}
}

void SelectSort(int R[],int n)//简单选择排序，从无序区中，选择最小的关键字，放到有序区中
{
	int i,j,k;
	for(i=0;i<n-1;i++)
	{
		k=i;
		for(j=i+1;j<n;j++)
		{
			if(R[j]<R[k])
			  k=j;
		}
		if(k!=i)
		{
			swap(R[i],R[k]);
		}
	}
}

void sift(int R[],int low,int high)
{
	int i=low,j=2*i;
	int tmp=R[i];
	while(j<=high)
	{
		if(j<high&&R[j]<R[j+1])//如果右孩子比较大 ，把j指向右孩子
		  j++;
		if(tmp<R[j])//根节点小于最大孩子的关键字
		{
			R[i]=R[j];//将R[j]调到双亲位置
			i=j;
			j=2*i;
		}
		else
		  break;//如果根结点大于等于最大孩子的关键字筛选结束
	}
	R[i]=tmp;//被筛选的结点放在最终位置
}
void HeapSort(int R[],int n)//堆排序
{
	int i;
	for(i=n/2;i>=1;i--)
	{
		sift(R,i,n);
	}
	for(i=n;i>=2;i--)
	{
		swap(R[1],R[i]);//将最后一个元素与跟R[1]交换
		sift(R,1,i-1);
	}
}

void Merge(int R[],int low,int mid,int high)
{
	int *R1;
	int i=low,j=mid+1,k=0;
	R1=(int *)malloc((high-low+1)*sizeof(int));
	while(i<=mid&&j<=high)
	{
		if(R[i]<=R[j])
		{
			R1[k]=R[i];
			i++;
			k++;
		}
		else
		{
			R1[k]=R[j];
			j++;
			k++;
		}
	}
	while(i<=mid)
	{
		R1[k]=R[i];
		i++;
		k++;
	}
	while(j<=high)
	{
		R1[k]=R[j];
		j++;
		k++;
	}
	for(k=0,i=low;i<=high;k++,i++)
	   R[i]=R1[k];
	free(R1);
}

void MergePass(int R[],int length,int n)
{
	int i;
	for(i=0;i+2*length-1<n;i=i+2*length)
	  Merge(R,i,i+length-1,i+2*length-1);
	if(i+length-1<n-1)
	  Merge(R,i,i+length-1,n-1);
}

void MergeSort(int R[],int n)
{
	int length;
	for(length=1;length<n;length=2*length)
	  MergePass(R,length,n);
}

int main()
{
	int R[MaxSize],R1[MaxSize];
	printf("\n\t随机产生50000个1-99的正整数，各整数按着从小到大的顺序排序\n");
	int n=50000;
	printf("\t---------------------------------------------------------\n");
	printf("\t排序方法             用时             是否正确           \n");
	printf("\t---------------------------------------------------------\n");
	initial(R,0,n-1);
	clock_t t;

	copy(R,R1,n);
    printf("\t直接插入排序\t");
	t=clock();
	InsertSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);

	copy(R,R1,n);
    printf("\t折半插入排序\t");
	t=clock();
	BinInsertSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


	copy(R,R1,n);
    printf("\t希尔排序\t");
	t=clock();
	ShellSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


	copy(R,R1,n);
    printf("\t冒泡排序\t");
	t=clock();
	BubbleSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


    copy(R,R1,n);
	printf("\t改进冒泡排序\t");
	t=clock();
	GBubbleSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


	copy(R,R1,n);
	printf("\t快速排序\t");
	t=clock();
	QuickSort(R1,0,n-1);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);

	copy(R,R1,n);
    printf("\t简单选择排序\t");
	t=clock();
	SelectSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


	copy1(R,R1,n);
    printf("\t堆排序  \t");
	t=clock();
	HeapSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);


	copy(R,R1,n);
    printf("\t二路归并排序\t");
	t=clock();
	MergeSort(R1,n);
	t=clock()-t;
	printf("   %lf秒",((float)t)/CLOCKS_PER_SEC);
    test(R1,0,n-1);

	printf("\t---------------------------------------------------------\n");
	return 1;
}