59++++++&&##^^.cpp

用 插入排序, 希尔排序 ,冒泡, 快速排序 , 选择排序 ,堆排序, 归并排序 实现对任意随机数序列,并比较各种方法的运行快慢和复杂度

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include<limits.h>
#include<stdio.h>
#include <conio.h>
const long      MAXITEM=30000;
void insertsort(long  r[],long  n)//排序元素r[1]-r[n]
{
	long  i,j;
	for(i=2;i<=n;i++)
	{
		r[0]=r[i];// r[0]监视哨
		j=i-1;
		while(r[0]<r[j])//元素移动,腾出位置插入r[0]
		{
			r[j+1]=r[j];
			j--;
			
		}
		r[j+1]=r[0];
	}
}
//希尔排序
void shellsort(long  r[],long  n)
{
long  i,j,gap;
long  temp;
gap=n/2;
while(gap>0)
{
	for(i=gap+1;i<=n;i++)
	{
		j=i-gap;
		while(j>0)
			if(r[j]>r[j+gap])
			{
				temp=r[j];
				r[j]=r[j+gap];
				r[j+gap]=temp;
				j=j-gap;
			}
			else j=0;
	}
	gap=gap/2;
}
}
//交换排序冒泡排序
void bubblesort(long  r[],long  n)
{
	long  i,j,exchange;
	long  temp;
	for(i=1;i<=n-1;i++)
	{
		exchange=0;
		for(j=n;j>=i+1;j--)
			if(r[j]<r[j-1])
			{
				temp=r[j];
				r[j]=r[j-1];
				r[j-1]=temp;
				exchange=1;
			}
			if(exchange==0)
				return;
	}
}
//快速排序
void quicksort(long  r[],long  s,long  t)//把r[s]-r[t]的元素进行快速排序
{ 
	long  i=s,j=t;
	if(s<t)
	{
		r[0]=r[s];//以为r[0]基准将r分为两部分
		do
		{
			while(j>i&&r[j]>=r[0])//从右向左找大于基准的记录r[j]
			j--;
			if(i<j)
			{
				r[i]=r[j];i++;
			}
			while(i<j&&r[i]<=r[0])
				i++;
			if(i<j)
			{
				r[j]=r[i];j--;
			}
		}while(i<j);
		r[i]=r[0];
		quicksort(r,s,j-1);
		quicksort(r,j+1,t);
	}
}
//直接选择排序
void selectsort(long  r[],long  n)
{
	long  i,j,k;
	long  temp;
	for(i=1;i<=n-1;i++)
	{
		k=i;
		for(j=i+1;j<=n;j++)
			if(r[j]<r[k])
				k=j;
			temp=r[i];
			r[i]=r[k];
			r[k]=temp;
	}
}
//堆排序
//建堆
void sift(long  r[],long  l,long  m)
{
	long  i,j;
	long  x;
	i=l;
	j=2*i;
	x=r[i];
	while(j<m)
	{
		if(j<m&&r[j]<r[j+1])
			j++;//若右孩子较大,则把J修改为右孩子的下标
		if(x<r[j])
		{
			r[i]=r[j];
			i=j;
			j=2*i;
		}
		else j=m+1;
	}
	r[i]=x;
}
void heapsort(long  r[],long  n)
{
	long  i;
	long  m;
	for(i=n/2;i>=1;i--)
		sift(r,i,n);
	for(i=n;i>=2;i--)
	{
		m=r[i];
		r[i]=r[1];
		r[1]=m;
		sift(r,1,i-1);
	}
}
//归并排序
void merge1(long  a[],long  s,long  m,long  n,long  b[])
{
	long i,j,k;
	i=s;j=m+1;k=0;
	while(i<=m&&j<=n)
		if(a[i]<=a[j])b[k++]=a[i++];
		else b[k++]=a[j++];
		while(i<=m)b[k++]=a[i++];
		while(j<=n)b[k++]=a[j++];
		return;
}
void merge2(long a[],long p1,long p2,long len,long b[])
{
	long i,j,k;
	i=p1;
	k=0;
	while(i+2*len-1<=p2)
	{
		merge1(a,i,i+len-1,i+2*len-1,b+k);
		i+=2*len;
		k+=2*len;
	}
	if(i+len<=p2)
		merge1(a,i,i+len-1,p2,b+k);
	else 
	{
		for(j=i;j<=p2;j++)b[k++]=a[j];
	}
}
void merge3(long a[],long p1,long p2,long b[])
{
	long len;
	len=1;
	while(len<p2-p1+1)
	{
		merge2(a,p1,p2,len,b);
		len=len*2;
		merge2(b,0,p2-p1,len,a+p1);
	}
}


void main()
{

    long  str[MAXITEM+1];
	long  str1[MAXITEM+1];
	long  str2[MAXITEM+1];
	long  str3[MAXITEM+1];
	long  str4[MAXITEM+1];
	long  str5[MAXITEM+1];
	long  str6[MAXITEM+1];
	long  str7[MAXITEM+1];
//	long  str8[MAXITEM+1];
	clock_t start,end;
    char ch,ch2='y';int ch1;
	long  i,num;
	cout<<"输入随机数的个数:"<<endl;
	cin>>num;
	for(i=1;i<=num;i++)
	{
		str[i]=rand();
		str1[i]=str[i];
		str2[i]=str[i];
		str3[i]=str[i];
		str4[i]=str[i];
		str5[i]=str[i];
		str6[i]=str[i];
		//cout<<str[i]<<" ";
	}
	cout<<endl;
cout<<"要查看产生的随机整数序列吗? 是(y)/不(n),如果需要继续往下查看,按任意键"<<endl;
cin>>ch;
if(ch=='y'||ch=='Y'){
  for(i=1;i<=num;i++)
   {
	   cout<<str[i]<<" ";
	   if(i%1000==0)getch();
   }
}     cout<<endl;
while(1)
{
      if(ch2=='n'||ch2=='N')break;
	  cout << "    ***********************选择排序方法******************** " <<endl
		   << "    1 插入排序  " <<endl      
		   << "    2 希尔排序  " <<endl 
		   << "    3 冒泡排序  " <<endl
           << "    4 快速排序  " <<endl
		   << "    5 选择排序  " <<endl
		   << "    6 堆排序    " <<endl
           << "    7 归并排序  " <<endl
		   
		   << "    ******************************************************** " <<endl;
	  cin>>ch1;
	  switch(ch1){
	  case 1:
    start=clock();
	insertsort(str,num);
	end=clock();
	cout<<endl<<"插入排序运行时间为"<<endl;
    printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
    cout<<"要查看插入排序后的序列吗? y(yes)/n(no)如果选择查看,需要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;

/*	for(i=1;i<=MAXITEM;i++)
	{
	
		cout<<str1[i]<<" ";
	}*/
	  case 2:
	cout<<endl;
    start=clock();

	shellsort(str1,num);
	end=clock();
	cout<<endl<<"希尔排序所用时间为"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
cout<<"要查看希尔排序后的序列吗? y(yes)/n(no)如果选择查看,需要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str1[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;
	  case 3:
	cout<<endl;
	start=clock();
bubblesort(str2,num);
end=clock();
	cout<<" 冒泡排序所用时间为"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
   cout<<"要查看冒泡排序后的序列吗? y(yes)/n(no)如果选择查看,如要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str2[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	}
	break;
	  case 4:
    cout<<endl;
start=clock();
	quicksort(str3,1,num);
end=clock();
	cout<<" 快速排序所用时间为"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
cout<<"要快速排序后的序列吗? y(yes)/n(no)如果选择查看,如要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str3[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	}
	  case 5:
	start=clock();

	selectsort(str4,num);
end=clock();
	cout<<endl<<" 选择排序所用时间为"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
  cout<<"要查看选择排序后的序列吗? y(yes)/n(no)如果选择查看,如要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str4[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;
	  case 6:
	start=clock();

	sift(str5,1,num);
	heapsort(str5,num);
	end=clock();
	cout<<endl<<" 堆排序所用时间为"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
cout<<"要查看堆排序后的序列吗? y(yes)/n(no)如果选择查看,需要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str5[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;
	  case 7:

	cout<<endl;
		start=clock();			
	merge3(str6,1,num, str7);
end=clock();

	cout<<"归并排序所用时间"<<endl;
	printf("time was: %f\n", (double)(end-start)/CLOCKS_PER_SEC);
	cout<<"要查看归并排序后的序列吗? y(yes)/n(no)选择查看序列,如要继续往下查看,按任意键"<<endl;
	cin>>ch;
	if(ch=='y'||ch=='Y')
	{
		for(i=1;i<=num;i++)
	{
		
		cout<<str6[i]<<" ";
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;
	  default:
		  break;
		  }
		  cout<<endl<<"还要继续用其他方法排序数列吗? y/n"<<endl;
		  cin>>ch2;
		  }

	return;
}