算法-基于比较的排序算法的实现和性能比较

活动地址：毕业季·进击的技术er

最近有朋友问到算法的排序问题，统一整合到一个设计里面怎么实现？我们首先要了解都有哪些内部排序算法，这些算法它的思想是什么？那这个教材都有，这里就不解释了，主要以下面一个设计例题来和大家讨论。【代码经过整合和修改以及多编辑器的调试，精简版】

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

基于比较的排序算法的实现和性能比较
1、分别实现插入排序、选择排序、堆排序、合并排序、快速排序，以不同规模(100，1000,2000,5000，10000，100000个数据)的随机数作为测试数据集，分别设置比较操作计数器。

 #define _CRT_SECURE_NO_WARNINGS 1 
   #include   
   #include   
   #include 
   #include  
   #include 
  
   #define MAX_SIZE 100000
   
   typedef struct SeqList
   
   {
   
   	int *r;//r[0]闲置
   
   	int length;//顺序表总长度
   
   }SeqList;
   
    
   
   enum OP
   
   {
   
   	EXIT,      //输入 
   
   	INSERT,    //插入 
   	
   	SELECT,    //选择 

   	STACK,     //堆 
   	
   	MERGE,     //归并 
   	
	QUICK,     //快速 
   
   };
   
   //建立并初始化线性表
   
   void InitSeqList(SeqList* L)
   
   {
   
   	assert(L);//检验指针有效性
   
   	L->r = (int *)malloc(MAX_SIZE*sizeof(int));//动态分配空间
   
   	if (!L->r)
   
   	{
   
   		printf("开辟空间失败！");
   
   		return;
   
   	}
   
   	L->length = 0;
   
   }
   
   //产生随机数并显示在界面上
   
   void CreateShow(SeqList* L)
   
   {
   
   	assert(L);
   
   	int i = 0, n;
   
   	printf("请输入要排序的元素个数>");
   
   	scanf("%d", &n);
   
   	for (; i <= n; i++)
   
   	{
	   L->r[i] = rand();//产生随机数
   
   	}
   
   	printf("n");
   
   	printf("随机产生了%d个随机数，它们分别是:n", n);
   
   	for (i = 1; i <= n; i++)
   
   	{
   
   		printf("%8d  ", L->r[i]);
   
   	}
   
   	printf("n");
   
   	L->length = n;
   
   }
   
  //打印出排序后的数据
   
void PrintSeqList(SeqList* L)
   
   {
   
   	assert(L);
   
   	printf("数据个数为:%dn", L->length);
   
   	printf("排序后的数据为(从小到大排序):n");
   
   	for (int i = 1; i <= L->length; i++)
   
   	{
   
   		printf("%8d  ", L->r[i]);
   
   	}
   
   	printf("n");
   
   }
   
   //交换两个数
   
void swap(int* num1, int* num2)
   
   {
   
   	int temp = *num1;
   
   	*num1 = *num2;
   
   	*num2 = temp;
   
   } //插入排序
   
   
   
void  maopao(SeqList *L) 
{ 
	for(int i=0;ilength - 1;i++) 
	{ 	
		for(int j=0;jlength - i;j++) 	
		{ 		
			if(L->r[i] > L->r[i + 1]) 		
			{ 			
				swap(&L->r[i], &L->r[i + 1]);
   			} 	
		} 					
	} 
} //快速排序
   
void QuickSort(SeqList* L, int low, int high)
   {
   
   	assert(L);
   
   	int mid;
   
   	int left = low;
   
   	int right = high;
   
   	if (L->length == 0)
   
   	{
   
   		printf("要排序的数据为空！");
   
   		return;
   
   	}
   
   	mid = L->r[low - (low - high) / 2];//选取的参照中间值
   
   	do
   
   	{
   
   		while (L->r[left] < mid && left < high)//从左到右找比mid大的元素
   
   			left++;
   
   		while (L->r[right] > mid && right > low)//从右到左找比mid小的元素
   
   			right--;
   
   		if (left <= right) //若找到且满足条件，则交换
   
   		{
   
   			swap(&L->r[left++], &L->r[right--]);
   
   		}
   
   	} 
	while (left <= right);
   
   	if (left < high)
   
   		QuickSort(L, left, high); //运用递归
   
   	if (low < right)
   
   		QuickSort(L, low, right);
   
   } //选择排序 
   
void SelectSort(SeqList *L) 

{ 	

	assert(L); 
	
	int i; 	
	
	int k;

	for(i=1;ilength;++i)     //选择第i个小的记录，并交换到位  
	
	{ 	
		int j=i;       //j用于记录最小元素的位置  	

 	for(k=i+1;k<=L->length;k++)        //在数组中选择key最小的元素  		
			   
	if(L->r[k]r[j])
   	
	   j=k;
	   
   	if(i!=j)              //第i个小的记录L->r[j]与第i个记录交换 
   				
	{
   					
   		swap(&L->r[i], &L->r[j]);
   			
   	} 	
   	
	} 	 
	
} //堆排序 

void HeapAdjust(SeqList*L,int s,int m)    //调整L->r[s]的关键字，使L->r[s-m]成为大顶堆  

{ 	

	assert(L);  	
	
	int i; 	
	
	L->r[0] = L->r[s]; 	
	
	for(i=2*s;i<=m;i*=2)      //沿数据较大的孩子结点向下筛选  
	
	{ 		
	
	if(ir[i] < L->r[i+1]))      //i为数据较大的记录下标  	
		
	i++; 	
		
	if(L->r[0] >= L->r[i])     //L->r[0]插入在s位置上 
	
	break; 	 
					
	L->r[s] = L->r[i]; 	 
			
	s=i; 
				
	} 
					
	L->r[s] = L->r[0]; //插入新数据  
						
}
   
   void HeapSort(SeqList*L) { 	assert(L); 	int i; 	if (L->length == 0)
   	{ 		printf("没有数据！"); 		return ; 	} 	for(i = L->length /2;i>0;i--)
   	
   		HeapAdjust(L,i,L->length); 	for(i = L->length;i>1;i--) 	
	 {
   			
   		swap(&L->r[1],&L->r[i]);//将堆顶记录和当前未经排序的子序列L->r[l..i]中最后一个记录互换 
   		
   		HeapAdjust(L,i,i-1);//将L->r[l..i-1] 重整调整为大顶堆  	
   		
		   } 
		   
		   } //归并排序函数的具体实现 
		   
void MergeArray(SeqList*L,int low,int mid,int high)

    { 	
    
	assert(L);
	
	int i,j,k,len1,len2; 
	   	
	int *front,*back; 	
	
	len1 = mid-low+1;//前一部分的长度
   	
	len2 = high-mid;//后一部分的长度  	
   	
	front =(int*)malloc(len1*sizeof(int));//申请两个空间存放排好的数据  
   	
	back =(int*)malloc(len2*sizeof(int)); 	//将数组转入两个新空间中  	
   
   for(i=0;ir[low+i]; 
		   	
		for(j=0;j<=len2;j++) 
		   		
		back[j] =L->r[mid+j+1]; 	//合并元素 
		    	
		i=0; 
		   	
		j=0; 
		   	
		k=low; 
		   	
while(i
	   //L->r[]中依次放入两个数组中较小的数  
	   		
	if(front[i]r[k++]=front[i++]; 	
   			
	else 
				   		
		L->r[k++]=back[j++]; 
				   	
} 	//将剩余元素合并
   			
   	while(ir[k++]=front[i++]; 
	   	
		   	while(jr[k++]=back[j++]; } //归并函数排序函数的具体实现  
   		
void MergeSort(SeqList*L,int low,int high) 

{ 	
   
   	assert(L); 
	   	
   	int middle;
   
   	if(L->length == 0) 	
   	
	   { 	
	   	
	   printf("要排序的数据为空！"); 
	   		
	   return; 
	   	
	   }
	   
   	if(low 		
	   	middle=low-(low-high)/2;
	   	
   		MergeSort(L,low,middle);//将前面一部分用递归的方法排序 
   		
   		MergeSort(L,middle+1,high);//将后面一部分用递归的方法排序 
   		
   		MergeArray(L,low,middle,high);//再将两个有序数列合并  
		   
		}
}
		   	
void menu()   //主菜单 
   
{
   
   	printf("nt***************算法排序比较系统***************");
   
   	printf("nt--------------------------------------------n");
   
   	printf("t***********       1、插入排序      ***********n");
   
   	printf("t***********       2、选择排序      ***********n");
   
   	printf("t***********       3、堆排序        ***********n");
   
   	printf("t***********       4、归并排序      ***********n");
   
   	printf("t***********       5、快速排序      ***********n");
   
   	printf("t***********       0、退出系统      ***********n");
   
}
   
   int main()
   
   {
   	
   	SeqList L;
   
	srand((unsigned int)time(NULL));
   
   	InitSeqList(&L);//初始化L
   
   	int n = 1;
   
   	clock_t start, end; //clock_t用于计时开始时间和结束时间 
   
   	while (n)
   
   	{
   
   		menu();
   
   		printf("请选择你要排序的方式（数字1~5）或退出系统（数字0）:");
   
   		scanf("%d", &n);
   
   		switch (n)
   
   		{
   
   		case INSERT:
   
   			start = clock();
   
   			CreateShow(&L);
   
   			end = clock();
   
   			PrintSeqList(&L);
   
   			printf("插入排序时间是:%f毫秒n", (float)(end - start));
   
   			break;
   
   		case SELECT:
   
   			start = clock();
   
   			CreateShow(&L);
   
   			SelectSort(&L);
   
   			end = clock();
   
   			PrintSeqList(&L);
   
   			printf("插入排序时间是:%f毫秒n", (float)(end - start));
   
   			break;
   
   		case STACK:
   
   			start = clock();
   
   			CreateShow(&L);
   
   			HeapSort(&L);
   
   			end = clock();
   
   			PrintSeqList(&L);
   
   			printf("插入排序时间是:%f毫秒n", (float)(end - start));
   
   			break;
   
   		case MERGE:
   
   			start = clock();
   
   			CreateShow(&L);
   
   			MergeSort(&L, 1, L.length);
   
   			end = clock();
   
   			PrintSeqList(&L);
   
   			printf("插入排序时间是:%f毫秒n", (float)(end - start));
   
   			break;
   			
   		case QUICK:
   
   			start = clock();
   
   			CreateShow(&L);
   
   			QuickSort(&L, 1, L.length);
   
   			end = clock();
   
   			PrintSeqList(&L);
   
   			printf("插入排序时间是:%f毫秒n", (float)(end - start));
   
   			break;
   
   		case EXIT:printf("感谢使用本系统，欢迎下次使用！"); break;
   
   		default:printf("您输入的序号错误！请重新选择:n"); break;
   
   		}
   
   	}
   
   	system("pause");
   
   	return 0;
   
   }

活动地址：毕业季·进击的技术er