multisort.cpp

分别用LSD-归并（可选其他内部排序方法）、LSD-分配收集、MSD-归并（可选其他排序方法）

// MultiSort.cpp : Defines the class behaviors for the application.
//

#include "stdafx.h"
#include "MultiSort.h"
#include "MultiSortDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
CString result;
/////////////////////////////////////////////////////////////////////////////
// CMultiSortApp

BEGIN_MESSAGE_MAP(CMultiSortApp, CWinApp)
	//{{AFX_MSG_MAP(CMultiSortApp)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG
	ON_COMMAND(ID_HELP, CWinApp::OnHelp)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMultiSortApp construction

CMultiSortApp::CMultiSortApp()
{
	// TODO: add construction code here,
	// Place all significant initialization in InitInstance
}

/////////////////////////////////////////////////////////////////////////////
// The one and only CMultiSortApp object

CMultiSortApp theApp;

/////////////////////////////////////////////////////////////////////////////
// CMultiSortApp initialization

BOOL CMultiSortApp::InitInstance()
{
	AfxEnableControlContainer();

	// Standard initialization
	// If you are not using these features and wish to reduce the size
	//  of your final executable, you should remove from the following
	//  the specific initialization routines you do not need.

#ifdef _AFXDLL
	Enable3dControls();			// Call this when using MFC in a shared DLL
#else
	Enable3dControlsStatic();	// Call this when linking to MFC statically
#endif

	CMultiSortDlg dlg;
	m_pMainWnd = &dlg;
	int nResponse = dlg.DoModal();
	if (nResponse == IDOK)
	{
		// TODO: Place code here to handle when the dialog is
		//  dismissed with OK
	}
	else if (nResponse == IDCANCEL)
	{
		// TODO: Place code here to handle when the dialog is
		//  dismissed with Cancel
	}

	// Since the dialog has been closed, return FALSE so that we exit the
	//  application, rather than start the application's message pump.
	return FALSE;
}

void Sort::Init()
{
	for(int i=0;i<10000;i++)
		for(int j=0;j<5;j++)
			msort[i].data[j]=0;
}
void Sort::ChangetoInt(CString text)
{
	char *p=text.GetBuffer(0);
	CString num;
	int i=0,j=0;
	while(*p&&i<size)
	{
		if(*p==' ')
			while(*p&&*p==' ')p++;
		if(*p=='\r')
		{
			p+=2;
			i++;
			continue;
		}
		while(*p&&*p!=' '&&*p!='\r')
		{
			num+=*p;
			p++;
		}
		msort[i].data[j]=atoi(num);
		num.Empty();
		j++;
		if(*p=='/r'||j>=keynum)
		{
			p++;
			if(*p&&*p!='\n')
				while(*p&&*p!='\n')p++;
			p++;
			i++;j=0;
		}	
	}
}
int Sort::LSDsort_a()
{
	int time=0;
 	for(int i=keynum-1;i>=0;i--)
		time+=comb(priority[i]-1,0,size-1);   //对每个关键字进行归并排序
	return time;		                      //返回比较次数和交换次数之和
}
int Sort::MSDsort()
{
	int time=0;
	int i=0;
	int j=0;
	int k=0;
	int start;
	time+=comb(priority[i]-1,0,size-1);    //对第一个关键字进行归并排序
	for(i=1;i<keynum;i++)
	{
		start=0;
		j=1;
		while(j<size)
		{
			while(j<size)
			{
				k=i-1;
				while(k>=0&&msort[j].data[priority[k]-1]==msort[start].data[priority[k]-1]){time++;k--;}
				//当所排过的关键字全部相等时，j++
				time++;
				if(k<0)j++;
				else break;    //不满足上述条件时，从start到j-1拿去归并排序
			}
			time+=comb(priority[i]-1,start,j-1);
			start=j;
			j++;
		}
	}
	return time;
}
int Sort::comb(int x,int start,int end)                 //归并排序
{
	int time=0;
	struct Data tempsort[10000];
	int len=1;
	int i=start;
	while(len<=end-start)
	{
		time+=combPass(msort,tempsort,x,len,start,end);
		len*=2;
		time+=combPass(tempsort,msort,x,len,start,end);
		len*=2;
	}
	return time;
}
int Sort::combPass(struct Data sortA[],struct Data sortB[],int x,int len,int start,int end)
{	//一趟归并排序
	int i=start;
	int time=0;
	while(i+2*len-1<=end)
	{
		time+=combine(sortA,sortB,i,i+len-1,i+2*len-1,x);
		i+=2*len;
	}
	if(i+len-1<=end)time+=combine(sortA,sortB,i,i+len-1,end,x);
	else for(int j=i;j<=end;j++)
	{
		time++;
		sortB[j]=sortA[j];
	}
	return time;
}

int Sort::combine(struct Data sortA[],struct Data sortB[],int x,int y,int z,int key)
{
	int i,j;
	int time=0;
	for(i=x,j=y+1;x<=y&&j<=z;i++,time++)
	{
		if(sortA[x].data[key]<=sortA[j].data[key])sortB[i]=sortA[x++];
		else sortB[i]=sortA[j++];
	}
	if(x<=y)
		for(;x<=y;x++,i++,time++)sortB[i]=sortA[x];
	if(j<=z)
		for(;j<=z;j++,i++,time++)sortB[i]=sortA[j];
	return time;
}
CString Sort::Result()
{
	CString result;
	CString a;
	CString temp;
	int i,j;
	for(i=0;i<size;i++)
	{
		for(j=0;j<keynum;j++)
		{	
			a.Format("%3d",msort[i].data[j]);
			temp+=a+" ";                   //result+=a+" ";
		}
		result+=temp+"\r\n";
		temp.Empty();
	}
	return result;
}
CString Sort::Result(int head)
{
	CString result;
	CString a;
	CString temp;
	int i,j;
	for(i=head;i>=0;i=msort[i].next)
	{
		for(j=0;j<keynum;j++)
		{
			a.Format("%3d",msort[i].data[j]);
			temp+=a+" ";
		}
		result+=temp+"\r\n";
		temp.Empty();
	}
	return result;
}
int Sort::LSDsort_b(int &head)
{
	int time=0;                            //返回关键步骤的进行次数
	for(int i=0;i<size-1;i++,time++)       
		msort[i].next=i+1;                 //静态链表初始化
	msort[i].next=-1;
 	for(i=keynum-1;i>=0;i--)
		time+=disclt(priority[i]-1,head);  //对每个关键字进行分配-收集
	return time;
}
int Sort::disclt(int x,int &head)
{
	int time=0;
	int h=head;
	int tail;
	struct Distribute dishead[101];
	int p,q;
	for(int i=0;i<101;i++,time++)
		dishead[i].tail=dishead[i].next=-1;   //将分配使用的101个链表头初始化
	while(h!=-1)                         //分配
	{
		p=msort[h].data[x];
		q=dishead[p].next;
		if(q==-1)dishead[p].tail=dishead[p].next=h;
		else
		{
			msort[dishead[p].tail].next=h;
			dishead[p].tail=h;
		}
		q=h;
		h=msort[h].next;
		msort[q].next=-1;
		time++;
	}
	head=-1;
	for(i=0;i<101;i++,time++)             //收集
	{
		if(dishead[i].next!=-1)
		{
			if(head==-1)
			{
				head=dishead[i].next;
				tail=head;
			}
			else msort[tail].next=dishead[i].next;
			tail=dishead[i].tail;
		}
	}
	return time;

}