大二数据结构排序作业

通过对数据结构的学习，本程序将7种常见的排序算法整理结合在一起，通过比较同一数据下的排序所需要的时间和交换比较次数，更加明显的认识到各种排序算法的优劣，文末有生成的随机数提供。

#include<bits/stdc++.h>
using namespace std;
int l[10000000];
long long length,com=0,move=0,t;//数据存储，长度，比较次数，移动次数。
void insertsort(int *l) //直接插入排序。
{
	com=move=0;
	for(int i=2;i<=length;i++)
	{
		com++;
		if(l[i]<l[i-1])
		{
			l[0]=l[i];
			l[i]=l[i-1];
			move++;
			int j; 
			for(j=i-2;l[0]<l[j];j--)
			{
				l[j+1]=l[j];
				move++;
				//com++;	
			}
			l[j+1]=l[0];	
		}	
	} 
	printf("直接插入排序的比较次数：%lld\n\n",com);
	printf("直接插入排序的移动次数：%lld\n\n",move);
} 
void binsertsort(int *l)//折半插入排序 
{
	com=move=0;
	int low,high,mid;
	for(int i=2;i<=length;i++)
	{
		l[0]=l[i];
		low=1;high=i-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			com++;
			if(l[0]<l[mid]) high=mid-1;
			else low=mid+1;	
		}
		for(int j=i-1;j>=high+1;j--)
		{
			l[j+1]=l[j];
			move++;	
		}
		l[high+1]=l[0];
	} 
	printf("折半插入排序比较次数 ：%lld \n\n",com); 
	printf("折半插入排序移动次数 ：%lld \n\n",move);
}
void shellinsert(int *r,int dk)//希尔排序 
{
	for(int i=dk+1;i<=length;i++)
	{
		com++;
		if(r[i]<r[i-dk])
		{
			l[0]=l[i];
			int j;
			for(j=i-dk;j>0&&r[0]<r[j];j-=dk)
			{
				l[j+dk]=l[j];
				move++;
			}
			l[j+dk]=l[0];
		}
	}
}
void shellsort(int *l,int dt[],int t)
{
	com=move=0;
	for(int k=1;k<=t;k++)
		shellinsert(l,dt[k]);
	printf("希尔排序比较次数 ：%lld \n\n",com); 
 	printf("希尔插入排序移动次数 ：%lld \n\n",move);
}
void bubblesort(int *l)//冒泡排序 
{
	com=move=0;int t;
	for(int i=1;i<=length-1;i++)
	{
		for(int j=1;j<=length-i;j++)
		{
			com++;
			if(l[j]>l[j+1])
			{
				t=l[j];
				l[j]=l[j+1];
				l[j+1]=t;
				move=move+3;
			}
		}
	}
	printf("冒泡排序比较次数 ：%lld \n\n",com); 
 	printf("冒泡排序移动次数 ：%lld \n\n",move);
}
int partition(int *l,int low,int high)   //快速排序 
{
	l[0]=l[low];
	int pivotkey=l[low];
	while(low<high)
	{
		while(low<high&&l[high]>=pivotkey) 
		 {--high;com++;}
		l[low]=l[high];move++;com++;
		while(low<high&&l[low]<=pivotkey)  
		 {++low;com++;}
		l[high]=l[low];move++;com++;
	}
	l[low]=l[0];
	return low;	
}
void qsort(int *l,long low,long high)
{
	if(low<high)
	{   
		int pivotloc=partition(l,low,high);
		qsort(l,low,pivotloc-1);
		qsort(l,pivotloc+1,high);
	}
} 
void quicksort(int *l)
{
   com=move=0;
   qsort(l,1,length);
   	printf("快速排序比较次数 ：%lld \n\n",com); 
 	printf("快速排序移动次数 ：%lld \n\n",move);
}
void selectsort(int *l)       //简单选择排序 
{
	int i,j,k,t;
	com=move=0;
	for(i=1;i<=length;++i)
	{ 
	  k=i;  
	  for(j=i+1;j<=length;++j)
	  {
	  	com++;
	    if(l[j]<l[k]) k=j; 
	  }
	  if(k!=i)
	  {
	  	t=l[i]; 
	  	l[i]=l[k];
	  	l[k]=t;
	  	move+=3;
	  }
	} 
 	printf("简单选择排序比较次数 ：%lld \n\n",com); 
 	printf("简单选择排序移动次数 ：%lld \n\n",move);	
}
void heapadjust(int *l,int s,int m)   //堆排序 
{
	int rc=l[s];
	for(int j=2*s;j<=m;j*=2)
	{
		com++;
		if(j<m&&l[j]<l[j+1]) ++j;
		com++;
		if(rc>=l[j]) break;
		l[s]=l[j];
		s=j; 
	}
	  l[s]=rc;
}

void creatheap(int *l)
{
    long n=length;
	for(long i=n/2;i>0;--i)
	heapadjust(l,i,n);
}

void heapsort(int *l)
{
	com=move=0;
	creatheap(l);
	for(int i=length;i>1;--i)
	 {
	 	int x=l[1];
	 	l[1]=l[i];
	 	l[i]=x;
	 	move+=3;
	 	heapadjust(l,1,i-1);
	 }
	printf("堆排序比较次数 ：%lld \n\n",com); 
 	printf("堆排序移动次数 ：%lld \n\n",move);
} 
int main()
{
	int dt[100000],m,t;
	double start,end;
	printf("1.从文件中读取 \n\n");
	printf("2.升序数据 \n\n");
	printf("3.降序数据 \n\n");
	printf("4.手动输入数据\n\n");
	printf("请选择输入数据的方式：\n\n");
	cin>>m;
	switch(m)
	{
		case 1:
		{
			printf("输入排序数组长度length(100,10000,100000,1000000)：");
			cin>>length;
			if(length==100)
			{
				FILE *fp=fopen("100.txt","rb");
				for(long i=1;i<=length;i++)
       			fscanf(fp,"%ld",&l[i]);
			}
			if(length==10000)
			{
				FILE *fp=fopen("10000.txt","rb");
				for(long i=1;i<=length;i++)
       			fscanf(fp,"%ld",&l[i]);
			}
			if(length==100000)
			{
				FILE *fp=fopen("100000.txt","rb");
				for(long i=1;i<=length;i++)
       			fscanf(fp,"%ld",&l[i]);
			}
			if(length==1000000)
			{
				FILE *fp=fopen("1000000.txt","rb");
				for(long i=1;i<=length;i++)
       			fscanf(fp,"%ld",&l[i]);
			}
			break;
		}
		case 2:
		{
			printf("输入排序数组长度length(10000)：");
			cin>>length;
			for(long i=1;i<=length;i++)
     		l[i]=i;
			break;
		}
		case 3:{
			printf("输入排序数组长度length(10000)：");
			cin>>length;
			for(int i=1;i<=length;i++)
			l[i]=length-i+1;
			break;
		}
		case 4:{
			printf("输入需要排序的数据：");
			for(int i=1;i<=length;i++)
			cin>>l[i];
			break;
		}
	}
	printf("\n\n");
	printf("1.直接插入排序 \n\n");
	printf("2.折半插入排序 \n\n");
	printf("3.希尔排序\n\n");
	printf("4.冒泡排序\n\n");
	printf("5.快速排序\n\n");
	printf("6.简单选择排序\n\n");
	printf("7.堆排序\n\n");
	printf("选择排序方式: "); 
	cin>>m;
	switch(m)
	{
		case 1:{
			start=clock();
            insertsort(l);
	        end=clock(); 
            printf("直接插入排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 2:{
			start=clock();
            binsertsort(l);
	    	end=clock(); 
            printf("折半插入排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 3:{
			int t=log2(length+1)/1; 
 	        for(int k=1;k<=t;k++)
 	            dt[k]=pow(2,t-k+1)-1;
	        start=clock();
            shellsort(l,dt,t);
	        end=clock(); 
            printf("希尔排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 4:{
			start=clock();
            bubblesort(l);   
	        end=clock(); 
            printf("冒泡排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 5:{
			start=clock();
            quicksort(l); 
	        end=clock();  
            printf("快速排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 6:{
			start=clock();
		    selectsort(l);
		    end=clock(); 
		    printf("简单选择排序运行时间T:%lf \n\n",end-start);
//		    for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		}
		case 7:{
			start=clock();
			heapsort(l);
            end=clock(); 
            printf("堆排序运行时间T:%lf \n\n",end-start);
//            for(int i=1;i<=length;i++)
//            {
//            	printf("%d ",l[i]);
//			}
			break;
		} 
	}
	return 0;
}

100: 点击下载

10000: 点击下载

100000 :点击下载

1000000: 点击下载

10000000: 点击下载

排序结果(电脑不同结果也不一样)点击下载

打赏