qksort.cpp

一种新的快速排序方法

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

#include "stdafx.h"
#include "qksort.h"

#include "MainFrm.h"
#include "ChildFrm.h"
#include "qksortDoc.h"
#include "qksortView.h"

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

#define N 30
#define OTHER 3
class rec
{
public:
	long k;
	char other[OTHER];
};
rec r[N];
unsigned long id[N];

void qksort(unsigned long,unsigned long);
void myqksort();
void www();
CString s;
CFile mf;



/////////////////////////////////////////////////////////////////////////////
// CQksortApp

BEGIN_MESSAGE_MAP(CQksortApp, CWinApp)
	//{{AFX_MSG_MAP(CQksortApp)
	ON_COMMAND(ID_APP_ABOUT, OnAppAbout)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
	// Standard file based document commands
	ON_COMMAND(ID_FILE_NEW, CWinApp::OnFileNew)
	ON_COMMAND(ID_FILE_OPEN, CWinApp::OnFileOpen)
	// Standard print setup command
	ON_COMMAND(ID_FILE_PRINT_SETUP, CWinApp::OnFilePrintSetup)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CQksortApp construction

CQksortApp::CQksortApp()
{
	// TODO: add construction code here,
	// Place all significant initialization in InitInstance
	myqksort();

}

/////////////////////////////////////////////////////////////////////////////
// The one and only CQksortApp object

CQksortApp theApp;

/////////////////////////////////////////////////////////////////////////////
// CQksortApp initialization

BOOL CQksortApp::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

	// Change the registry key under which our settings are stored.
	// TODO: You should modify this string to be something appropriate
	// such as the name of your company or organization.
	SetRegistryKey(_T("Local AppWizard-Generated Applications"));

	LoadStdProfileSettings();  // Load standard INI file options (including MRU)

	// Register the application's document templates.  Document templates
	//  serve as the connection between documents, frame windows and views.

	CMultiDocTemplate* pDocTemplate;
	pDocTemplate = new CMultiDocTemplate(
		IDR_QKSORTTYPE,
		RUNTIME_CLASS(CQksortDoc),
		RUNTIME_CLASS(CChildFrame), // custom MDI child frame
		RUNTIME_CLASS(CQksortView));
	AddDocTemplate(pDocTemplate);

	// create main MDI Frame window
	CMainFrame* pMainFrame = new CMainFrame;
	if (!pMainFrame->LoadFrame(IDR_MAINFRAME))
		return FALSE;
	m_pMainWnd = pMainFrame;

	// Parse command line for standard shell commands, DDE, file open
	CCommandLineInfo cmdInfo;
	ParseCommandLine(cmdInfo);

	// Dispatch commands specified on the command line
	if (!ProcessShellCommand(cmdInfo))
		return FALSE;

	// The main window has been initialized, so show and update it.
	pMainFrame->ShowWindow(m_nCmdShow);
	pMainFrame->UpdateWindow();

	return TRUE;
}


/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
		// No message handlers
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

// App command to run the dialog
void CQksortApp::OnAppAbout()
{
	CAboutDlg aboutDlg;
	aboutDlg.DoModal();
}

/////////////////////////////////////////////////////////////////////////////
// CQksortApp message handlers
void trans(unsigned long m,unsigned long n)
{
	int u;
	r[m].k=r[n].k;
	for(u=0;u<OTHER;u++)
		r[m].other[u]=r[n].other[u];
}
void qkpass(unsigned long s,unsigned long t,unsigned long *k)
{
	unsigned long l=t;	*k=s;
	long x=r[s].k;
	rec tr;
	int m;
	tr.k=r[s].k;
	for(m=0;m<OTHER;m++)
		tr.other[m]=r[s].other[m];
	while(*k<l)
	{
		while(*k<l&&r[l].k>=x) l--;
		trans(*k,l);
		while(*k<l&&r[*k].k<=x) *k++;
		trans(l,*k);
	}
	r[*k].k=tr.k;
	for(m=0;m<OTHER;m++)
		r[*k].other[m]=tr.other[m];


}




void myqksort()
{
	unsigned long i;
	mf.Open("qksort.txt",CFile::modeCreate+CFile::modeWrite);
	srand(time(NULL));
	for(i=0L;i<N;i++)
	{
		id[i]=i;
		r[i].k=rand()*65536+rand();
	}
	www();
	qksort(0,N-1);
	www();
	mf.Close();

}

void www()
{
	unsigned long i;
	for(i=0L;i<N;i++)
	{
		//if(i%6==0) mf.Write("\n",1);
		s.Format("%ld  ",r[i].k);
		mf.Write(s,13);
	}
}

void qksort(unsigned long s,unsigned long t)
{
	unsigned long k;
	if(s<t)
	{
		qkpass(s,t,&k);
		qksort(s,k-1);
		qksort(k+1,t);
	}
}