4种算法.cpp

精心编写的带有4个基本算法的程序

#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;
void main()
{ void shellsort(int v[],int n);
  void insort(int v[],int n);
  void selectsort(int v[],int n);
  void bubble(int v[],int n);
  int i,j,a[100],n,z;
  int flag=1;
  char c;
  while(flag!=0)
  { cout<<"输入N:";
    cin>>n;
    cout<<endl;
    cout<<"产生"<<n<<"位1~100的随即数:"<<endl;
  srand((unsigned)time(0));               //srand和rand的用法
  for(i=0;i<n;i++)
  {if((i+1)%10==0)cout<<endl;
	j=rand()%99+1;
    cout<<setw(5)<<j;
	a[i]=j;
  }
  cout<<endl;
  cout<<"希尔排序(z=1)! 插入排序(z=2)! 选择排序(z=3)! 冒泡排序(z=4)! 快速排序(z=5)! "<<endl;
  cout<<"请输入z:";
  cin>>z;
  cout<<endl;
  switch(z)
  {case 1:
   cout<<"希尔排序后的数为:"<<endl;
   shellsort(a,n);break;
   case 2:
   cout<<"插入排序后的数为:"<<endl;
   insort(a,n);break;
   case 3:
	cout<<"选择排序后的数为:"<<endl;
	selectsort(a,n);break;
   case 4:
	cout<<"冒泡排序后的数为:"<<endl;
	bubble(a,n);break;
   default:cout<<"没正确输入数值!"<<endl;
  }
   for(i=0;i<n;i++)
	 {if((i+1)%10==0)cout<<endl;
	  cout<<setw(5)<<a[i];
  }
  cout<<endl;
  cout<<"是否还要继续请输入Y/N:";
  cin>>c;
  if(c=='n'||c=='N')
	  flag=0;
  }
}
void shellsort(int v[],int n)   //希尔排序算法
{ int gap,i,j,temp;             //经典算法，但是不稳定
  for(gap=n/2;gap>0;gap/=2)
  for(i=gap;i<n;i++)
  for(j=i-gap;j>=0&&v[j]>v[j+gap];j-=gap)
  {temp=v[j];v[j]=v[j+gap];v[j+gap]=temp;}
}
void insort(int v[],int n)   //直接插入排序算法  最坏情况下时间复杂度O(n^2)
{ int i,j,t;
  for(j=1;j<n;j++)
  for(i=j-1;i>=0&&v[i]>v[i+1];i--)
  {t=v[i];v[i]=v[i+1];v[i+1]=t;}
  
}
void selectsort(int v[],int n)  //选择排序算法    最坏情况下时间复杂度O(n^2)
{ int i,j,t;
  for(i=0;i<n-1;i++)
     for(j=i+1;j<n;j++)
		 if(v[i]>v[j])
		 {t=v[i];v[i]=v[j];v[j]=t;}
  
}
void bubble(int v[],int n)   //冒泡排序算法 时间复杂度O(n^2)
{ int i,j,t;
  for(j=0;j<n-1;j++)
	  for(i=0;i<n-1-j;i++)
		  if(v[i]>v[i+1])
		  {t=v[i];v[i]=v[i+1];v[i+1]=t;}
}