jdw.cpp

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

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include<limits.h>
#include<stdio.h>
#include <conio.h>
#include<fstream.h>
//const long* rand_file="rand.DAT";
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];//在J+1位置处插入r[0]
	}
}
//希尔排序
void shellsort(long  r[],long  n)//排序元素r[1]-r[n]
{
long  i,j,gap;
long  temp;  //temp为临时变量
gap=n/2;    //增量初值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]=r[j+gap];
				r[j+gap]=temp;
				j=j-gap;
			}
			else j=0;//通过给J赋值而退出while循环
	}
	gap=gap/2;//减少增量
}
}
//交换排序冒泡排序
void bubblesort(long  r[],long  n)//排序元素r[1]-r[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]=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])//从左向右找大于基准的记录r[i]
				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;//用K指出每趟在无序区段的最小元素
			temp=r[i];//将r[k],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;   //r[j]是r[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];  //将r[j]调到父亲的位置上
			i=j;         //修改i,j的值,以便继续向下筛 
			j=2*i;
		}
		else j=m+1;//筛运算完成,令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--)//进行n-1次循环完成堆排序
	{
		m=r[i];//将第一个元素同当前敬意内最后一个元素对换
		r[i]=r[1];
		r[1]=m;
		sift(r,1,i-1);//筛选r[1]结点,得到i-1个结点的堆
	}
}
//归并排序
void merge1(long  a[],long  s,long  m,long  n,long  b[])//二路合并,将有序段a[s]-a[m] 和a[m+1]-a[n]合并到b[0]-b[n-s]
{
	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[])//多段二路合并,a[p1]-a[p2]中,每len个元素为一个有序段,
{                                                     //将从头起的每个连续的两段分虽合并为一个有序段,存入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)           //剩两段,最最后的段长不足len
		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[])//二路归并排序,将a[p1]-a[p2]中的元素排序,结果在b[0]-b[p2-p1]中
{
	long len;
	len=1;
	while(len<p2-p1+1)
	{
		merge2(a,p1,p2,len,b);//将a[p1]-a[p2]中的长度为len 的相邻有序段两两合并到b[0]-b[p2-p1]
		len=len*2;
		merge2(b,0,p2-p1,len,a+p1);//将b[0]-b[p2-p1]中的长度为len 的相邻有序段两两合并到a[p1]-a[p2]
	}
}


void main()
{
	ifstream input_file;//输入文件流
	ofstream output_file;//输出文件流

    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];

	clock_t start,end;
    char ch,ch2='y';int ch1;
	long  i,num;
	
	cout<<"计算机科学与技术A班     陈婷    033511056"<<endl<<endl;
	cout<<"***************欢迎使用本程序****************"<<endl<<endl;

	cout<<"请输入随机数的个数(0~30000):"<<endl;
	cin>>num;
    output_file.open("rand_file.txt");
    if(!output_file){
	cout<<"不能打开文件rand_file.txt!"<<endl;
	return;
	}  
    output_file<<"未排序的随机数序列："<<endl;//将排序前的随机数写入文件rand_file
	for(i=1;i<=num;i++)
	{
		str[i]=rand();
		output_file<<str[i]<<" ";
		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<<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;
	output_file<<endl<<"插入排序后的随机数序列为："<<endl;
 	for(i=1;i<=num;i++)
	{
		output_file<<str[i]<<" ";
	}
	if(ch=='y'||ch=='Y')
	{
	for(i=1;i<=num;i++)
	{
		
		cout<<str[i]<<" ";
	
		if(i%1000==0)getch();//需要include <conio.h>
	}
	};
	break;


	  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;
	output_file<<endl<<"希尔排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str1[i]<<" ";
	}
	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;
	output_file<<endl<<"冒泡排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str2[i]<<" ";
		}
	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;
	output_file<<endl<<"快速排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str3[i]<<" ";
	}
	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;
	output_file<<endl<<"选择排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str4[i]<<" ";
	}
	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;
	output_file<<endl<<"堆排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str5[i]<<" ";
	}
	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;
	output_file<<endl<<"归并排序后的随机数序列为："<<endl;
	for(i=1;i<=num;i++)
	{
		output_file<<str6[i]<<" ";
	}
	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;
	      }
		  cout<<endl<<"   您可在查看生成的rand_file.txt文件以核对序列的正确性，谢谢使用本程序！！"<<endl;
		  return;
}