这是上算法设计时老师要求编的程序,我自己编的,希望大家看看,帮着改进一下!
原程序代码如下:
#include <afx.h>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;

int count,s_count=0;//count记录序列的数目，s_count记录逆对数目
string f_name;//存储序列的文件名
int *Sequence;//存储序列的数组

void number_in()//从文件中读取序列中的元素到数组中
{
ifstream file(f_name.c_str(),ios::in);
if(file.fail())
{
cout<<"文件不存在"<<endl;
exit(0);
}
file>>count;//读取序列的数目
cout<<"序列元素个数:"<<count<<endl;
Sequence=new int[count];
cout<<"Loading..."<<endl;
for(int i=0;i<count;i++)//将序列中的元素从文件中读入数组中
file>>Sequence[i];

}

void MergeSort(int p,int q)//排序，找逆对
{
int r=(p+q)/2;//计算p到q中间位置
int i=p,j=r+1,k=0;
int *T_Sequence=new int[q-p+1];//用于临时存储由大到小排好的序列
while(i<=r)
{
if(Sequence[i]>Sequence[j])//判断第i位数是否大于第j位(位数从0开始)
{
s_count+=q-j+1;//由于Sequence[i]>Sequence[j]，而Sequence[j]>Sequence[x],x=[j+1,...,q]
//所以在第p位到第q位中，第i位的逆对数为q-j+1
T_Sequence[k++]=Sequence[i++];//将较大的数存入临时的数组中
}
else
{
T_Sequence[k++]=Sequence[j++];//将将较大的数存入临时的数组中
if(j>q) goto end;
}
}
end:;
while(i<=r)
T_Sequence[k++]=Sequence[i++];//如果q到r位置上的数还有未存入临时数组的，则将其存入
q=p+k-1;//重新计算出需要排序的最末位
i=p,k=0;//准备将临时数组中已经排好的数重新存入数组Sequence中
while(i<=q)//将临时数组中由大到小排好的数重新存入Sequence中
Sequence[i++]=T_Sequence[k++];
}

void Merge(int p,int q)//递归
{
if(p<q)
{
int r=(p+q)/2;
Merge(p,r);
Merge(r+1,q);
MergeSort(p,q);
}
}

void Calculate()//载入计算的逆对，并记录时间和输出结果
{
CTime start,stop;
float s_time=0;//用于记录用于计算逆对所需的时间
cout<<endl<<"将计算的序列文件名:";
cin>>f_name;
number_in();//读取数
cout<<endl<<"Processing..."<<endl;
start=CTime::GetCurrentTime();//获取开始计算时的时间

Merge(0,count-1);

stop=CTime::GetCurrentTime();//获取结束时的时间
CTimeSpan diff=stop-start;//得到时间差
s_time=diff.GetTotalSeconds();//得到计算花费的时间
cout<<endl<<"The counts of inversions is:"<<s_count<<endl;//输出逆对的数目
cout<<"Time cost:"<<showpoint<<s_time<<"s"<<endl;//输出计算逆对花费的时间
}

void main()
{
Calculate();//调用计算逆对数目的函数
getchar();
}

[此贴子已经被作者于2007-10-29 23:34:42编辑过]