内部排序.cpp

来自「这个程序包括了各种常用内部排序算法在平均排序所需时间上的比较」· C++ 代码 · 共 225 行

#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#define   MAXSIZE   300000
int RandArray[MAXSIZE];
/**************随机生成函数**************/
void RandomNum()
{
	int i;
	srand((int)time(NULL));
	for(i=0;i<MAXSIZE;i++)
		RandArray[i]=(int)rand();
	return;
}
clock_t  t1,t2;
typedef   struct 
{ 
  int    r[MAXSIZE];//数组
 long    length;//长度
}Sqlist;//线性表
Sqlist a;
Sqlist B;

//直接插入排序
insertsort(struct rec r[],int n)
{
int i,j;
unsigned long int compare=0,move=0;
for(i=2;i<=n;i++)
   {compare++;
    r[0]=r[i];
    move++;
    j=i-1;
   while(r[0].key {r[j+1]=r[j];
j--;
move++;
++compare;}
   r[j+1]=r[0];
   move++;
   }
  printf("\nInsertSort compare= %ld,move= %ld\n",compare,move);
}

//起泡排序
void qipao_Sort(Sqlist &R)
{  int temp;
      for (int i=1; i<=R.length-1; i++ )
          for (int j=R.length;j>=i+1;j--)
                if(R.r[j]<R.r[j-1])
				//小于就交换
				{temp=R.r[j];
                 R.r[j]=R.r[j-1];
				 R.r[j-1]=temp;
				}
}
//选择排序
void select(Sqlist &R)
{int i,j ,k;int temp,min;
 for(i=1;i<R.length;i++)
 {k=i;
  min=R.r[i];
  for(j=i+1;j<=R.length;j++)
	  if(R.r[j]<min)
		  //选择一个最小的
	  {k=j;
	   min=R.r[j];
	  }

	  if(k!=i)
	   //将最小的和当前位置交换
	  {temp=R.r[k];
       R.r[k]=R.r[i];
	   R.r[i]=temp;
	 }
 }

}
void ShellSort(Sqlist &R)//希尔排序
{
	int  delta[30],t=0,temp=R.length,i;
	while(temp/2!=0)//得到增量数组的大小
{
   temp=temp/2;
   delta[t++]=temp;
}
    int  k,j,L;
for(k=0;k<t;k++)
 {
	L=delta[k];
   for(i=L+1;i<=R.length;i++)//每次对给定的增量进行插入排序
	  if(R.r[i]<R.r[i-L])
	  { 
		  R.r[0]=R.r[i];
	      for(j=i-L;j>0&&R.r[j]>R.r[0];j-=L)
		  R.r[j+L]=R.r[j];
		  
          R.r[j+L]=R.r[0];   
 	  }
 }
}
//快速排序
//找基准点位置
int  findpivot(int i,int j,Sqlist &R)
{int firstkey=R.r[i];
 int k;
 for(k=i+1;k<=j;k++)
	 if(R.r[k]>firstkey)return  k;
	 else  return  i;
	 return  0;
}

//根据基准点分割，返回分割点
int partition(int i,int j,int pivot, Sqlist &R)
{int low=i,high=j;int temp;
do{temp=R.r[low];
  R.r[low]=R.r[high];
  R.r[high]=temp;
  while(R.r[high]>=pivot)high--;
  //大于基准点的值放右边
  while(R.r[low]<pivot)low++;
   //小于基准点的值放左边
}while(low<=high);
return  low;
}

void quicksort(int i,int j,Sqlist &R)
{int pivot,pivotindex,k;
 pivotindex=findpivot(i,j,R);
 if(pivotindex)
 {pivot=R.r[pivotindex];
  k=partition(i,j,pivot,R);
  //找基准点位置
  quicksort(i,k-1,R);
  //递归左区间
  quicksort(k+1,j,R);
  //递归右区间
}
}
void quick_sort(Sqlist &R)
{
quicksort(1,R.length,R);
}
//堆排序,如A[first]加入建好的堆A[first+1]....A[last]
void  pushdown(int first,int  last, Sqlist &A)
{int r=first;int temp;
 while(r<=last/2)
       if((r==last/2)&&(last%2==0))//r只有一个儿子
	   { if(A.r[r]>A.r[2*r])
	   {temp=A.r[r];A.r[r]=A.r[2*r];A.r[2*r]=temp;}

	    r=last;
	   }
	else  if((A.r[r]>A.r[2*r])&&(A.r[2*r]<=A.r[2*r+1]))
		//左儿子和它交换
	{
	temp=A.r[r];A.r[r]=A.r[2*r];A.r[2*r]=temp;
	
	r=2*r;
	
	}
   else  if((A.r[r]>A.r[2*r+1])&&(A.r[2*r+1]<A.r[2*r]))
	//右儿子和它交换
	{
	 temp=A.r[r];A.r[r]=A.r[2*r+1];A.r[2*r+1]=temp;
	
	r=2*r+1;
	
	}
   else
	    r=last;
 
}
void sort_dui(Sqlist &A)
{int i,temp,n=A.length;
for(i=n/2;i>=1;i--)//建堆
    pushdown(i,n,A);
for(i=n;i>=2;i--)
{temp=A.r[1];
A.r[1]=A.r[i];
A.r[i]=temp;
pushdown(1,i-1,A); //调整堆
}
}
void  init_data(Sqlist &R)
{cout<<"请输入排序的数目:";
cin>>R.length;
int choose;long i;
	cout<<"请输入排序的数的产生方式\n";
cout<<"1:随机产生  2:正序     3:逆序\n";
cin>>choose;
switch(choose)
{
case 1:  srand((unsigned)time( NULL));
   //种子为系统时间
for( i=1;i<=R.length;i++ )
   R.r[i]=rand();break;
case  2:for(i=1;i<=R.length;i++ )
       R.r[i]=i;break;
case  3:for(i=1;i<=R.length;i++ )
       R.r[i]=R.length-i;break;
}
}
void main()
{
	int choose;
    cout<<"1:插入排序    2:冒泡排序   3:选择排序\n4:希尔排序    5:快速排序   6:堆排序\n7:退出\n";
    cin>>choose;
    while(choose!=7)
{
init_data(a);t1=clock(); 	
switch(choose)
{
  case 1:insertsort(a);break;
  case 2:qipao_Sort(a);break;
  case 3:select(a);break;
  case 4:ShellSort(a);break;
  case 5:quick_sort(a);break;
  case 6:sort_dui(a);break;
}
t2=clock();cout<<"时间:  "<<double(t2-t1)/CLK_TCK<<"秒"<<endl;
cout<<"1:插入排序     2:冒泡排序   3:选择排序\n4:希尔排序    5:快速排序    6:堆排序\n7: 退出\n";
cin>>choose;
}
}