排序结果没有问题,可是比较次数和移动次数的计数结果不对。求高人指点。
#include<iostream>
using namespace std;
class Sort
{
private:
int *r;
int n; // the number of elements of array
int MoveNum;
int CompNum;
public:
void insert();
void bubble();
int getn();
void quick(int,int);
void select();
void shell();
void ini();
int partion(int,int);
void Qsort(int,int);
~ Sort();
};
Sort::~Sort()
{
delete []r;
}
void Sort::ini()
{
int m;
cout<<"输入带排序数字的个数为 ";
cin>> m;
r=new int[m+1];
cout<<"输入待排序的"<<m<<"个数:"<<endl;
for (int i=1;i<=m;i++)
{
cin>>r[i];
}
n=m;
}
void Sort::insert()
{
MoveNum=0; CompNum=0;
for(int i=2;i<=n;i++)
if(r[i]<r[i-1])
{
r[0]=r[i];
for(int j=i-1;r[j]>r[0];j--)
{ r[j+1]=r[j];
MoveNum++;
}
r[j+1]=r[0];
}
CompNum=MoveNum;
cout<<"插入排序后的结果是";
for( i=1;i<=n;i++)
cout<<r[i]<<" ";
cout<<endl <<"移动次数为"<<MoveNum<<endl
<<"比较次数为"<<CompNum<<endl<<endl<<endl;
}
void Sort::shell()
{
MoveNum=0; CompNum=0;
for(int d=n/2;d>=1;d=d/2)
{
for(int k=d+1;k<=n;k++)
{
CompNum++;
if(r[k]<r[k-d])
{
r[0]=r[k];
int j=k-d;
for(;j>0&&r[0]<r[j];j=j-d)
{
r[j+d]=r[j];
MoveNum++;
}
r[j+d]=r[0];
}
}
}
cout<<"希尔排序后的结果是";
for(int i=1;i<=n;i++)
cout<<r[i]<<" ";
cout<<endl <<"移动次数为"<<MoveNum<<endl
<<"比较次数为"<<CompNum<<endl<<endl<<endl;
}
void Sort::bubble()
{
int count=0;
MoveNum=0;
CompNum=0;
int pos=n;
while(pos!=0)
{
int bound=pos;
pos=0;
for(int i=1;i<bound;i++)
{
CompNum++;
if(r[i]>r[i+1])
{
r[0]=r[i];
r[i]=r[i+1];
r[i+1]=r[0];
pos=i;count++;
}
}
}
MoveNum=count*3;
cout<<"冒泡排序后的结果是";
for( int i=1;i<=n;i++)
cout<<r[i]<<" ";
cout<<endl<<"移动次数为"<<MoveNum<<endl
<<"比较次数为"<<CompNum<<endl<<endl<<endl;
}
void Sort::quick(int i,int j)
{
if(i<j)
{
int loc=partion(i,j);
quick(i,loc-1);
quick(loc+1,j);
}
}
void Sort::Qsort(int i,int j)
{
MoveNum=0; CompNum=0;
quick(i,j);
cout<<"快速排序后的结果是";
for( i=1;i<=n;i++)
cout<<r[i]<<" ";
cout<<endl <<"移动次数为"<<MoveNum<<endl
<<"比较次数为"<<CompNum<<endl<<endl<<endl;
}
int Sort::partion(int first,int end)
{
int i=first;
int j=end;
int pivot=r[i];
while(i<j)
{
MoveNum++;
while((i<j)&&r[j]>=pivot)
{
j--; CompNum++;
}
r[i]=r[j]; MoveNum++;
while((i<j)&&r[i]<=pivot)
{
i++; CompNum++;
}
r[j]=r[i]; MoveNum++;
}
r[i]=pivot;
return i;
}
void Sort::select()
{
int count=0;
int MoveNum=0;int CompNum=0;
for(int i=1;i<n;i++)
{
int index=i;
for(int j=i+1;j<=n;j++)
{
if(r[j]<r[index])
index=j;
CompNum++;
}
if(index!=i)
{
r[0]=r[i];
r[i]=r[index];
r[index]=r[0];
count++;
}
}
MoveNum=count*3;
cout<<"选择排序后的结果是";
for(i=1;i<=n;i++)
cout<<r[i]<<" ";
cout<<endl <<"移动次数为"<<MoveNum<<endl
<<"比较次数为"<<CompNum<<endl<<endl<<endl;
}
int Sort::getn()
{
return n;
}
void main()
{
Sort sort;
sort.ini();
sort.insert();
sort.bubble();
int j=sort.getn();
sort.Qsort(1,j);
sort.select();
sort.shell();
}