//六种排序方法.
#include<iostream.h>
#define max 100
class sample
{
int A[max]; int n;
friend class process;
public:
sample() {n=0;}
};
class process
{ void qsort(sample &s,int l,int h); //私有成员,由quicksort()成员调用
public:
void getdata(sample &s); //获取数据
void insertsort(sample &s); //插入排序
void shellsort(sample &s); //希尔排序
void bubblesort(sample &s); //冒泡排序
void quicksort(sample &s); //快速排序
void selectsort(sample &s); //选择排序
void binsertsort(sample &s); //折半排序
void disp(sample &s); //输出结果
};
void process::getdata(sample &s)
{ int i; cout<<"元素个数: "; cin>>s.n;
for(i=0;i<s.n;i++)
{ cout<<"输入第 "<<i+1<<" 个数据: "; cin>>s.A[i]; }
}
void process::insertsort(sample &s) //插入排序
{ int i,j,temp;
for(i=0;i<s.n;i++)
{ temp=s.A[i]; j=i-1;
while (temp<s.A[j])
{ s.A[j+1]=s.A[j]; j--; }
s.A[j+1]=temp;
}
}
void process::shellsort(sample &s) //希尔排序
{ int i,j,gap,temp; gap=s.n/2;
while(gap>0)
{ for(i=gap;i<s.n;i++)
{ j=i-gap;
while (j>=gap)
if(s.A[j]>s.A[j+gap])
{ temp=s.A[j]; s.A[j]=s.A[j+gap]; s.A[j+gap]=temp; j=j-gap; }
else j=0;
}
gap=gap/2;
}
}
void process::bubblesort(sample &s) //冒泡排序
{ int j,i,temp;
for(i=0;i<s.n;i++)
for(j=s.n-1;j>i+1;j--)
{ if(s.A[j]<s.A[j-1])
{ temp=s.A[j]; s.A[j]=s.A[j-1]; s.A[j-1]=temp; }
}
}
void process::quicksort(sample &s) //快速排序
{ qsort(s,0,s.n-1); }
void process::qsort(sample &s,int l,int h)
{ int i=l,j=h,temp;
if(l<h)
{ temp=s.A[l];
do
{ while (j>i&&s.A[j]>=temp) j--;
if(i<j)
{ s.A[i]=s.A[j]; i++; }
while( i<j&&s.A[i]<=temp) i++;
if(i<j)
{ s.A[j]=s.A[i]; j--; }
}while(i<j);
s.A[i]=temp; qsort(s,l,j-1); qsort(s,j+1,h);
}
}
void process::selectsort(sample &s) //选择排序
{ int i,j,k,temp;
for(i=0;i<s.n;i++)
{ k=i;
for(j=i+1;j<s.n-1;j++)
if(s.A[j]<s.A[k]) k=j;
temp=s.A[i]; s.A[i]=s.A[k]; s.A[k]=temp;
}
}
void process::binsertsort(sample &s) //折半排序
{ int i,j,mid,high,low;
for(i=1;i<s.n;i++)
{ s.A[s.n]=s.A[i]; low=0; high=i-1;
while(low<=high)
{ mid=(low+high)/2;
if(s.A[s.n]<s.A[mid]) high=mid-1;
else low=mid+1;
}
for(j=i-1;j>=high;--j) s.A[j+1]=s.A[j];
s.A[high+1]=s.A[s.n];
}
}
void process::disp(sample &s)
{ int i; for(i=0;i<s.n;i++) cout<<s.A[i]<<" "; cout<<endl;}
void main()
{
int sel; char c; sample s; process p; p.getdata(s); cout<<"原来排序: "; p.disp(s);
do
{ cout<<"0: 插入排序 1:希尔排序 2:冒泡排序 3:快速排序 4:选择排序
5:折半排序 其他退出"<<endl;
cout<<"选择排序结果: "; cin>>sel;
switch(sel) {
case 0: p.insertsort(s); cout<<"插入排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
case 1: p.shellsort(s); cout<<"希尔排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
case 2: p.bubblesort(s); cout<<"冒泡排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
case 3: p.quicksort(s); cout<<"快速排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
case 4: p.selectsort(s); cout<<"选择排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
case 5: p. binsertsort (s); cout<<"折半排序结果: "; p.disp(s);
cout<<"是(y/Y)否继续: "; cin>>c; break;
default: c='n'; break;
}
if(c!='y'&&c!='Y') cout<<"退出排序!"<<endl;
}while(c=='y'||c=='Y');
}
