问题描述

关于c++几种简单排序算法的比较次数和移动次数的问题

排序结果没有问题，可是比较次数和移动次数的计数结果不对。求高人指点。

#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();

}

解决方案

文学韭·11111111111111111111111111