sort_comparedlg.cpp

常用的几种排序算法的实现源码

// sort_compareDlg.cpp : implementation file
//

#include "stdafx.h"
#include "sort_compare.h"
#include "sort_compareDlg.h"

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

/////////////////////////////////////////////////////////////////////////////
// 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)
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CSort_compareDlg dialog

CSort_compareDlg::CSort_compareDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CSort_compareDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CSort_compareDlg)
	m_dBubble_com = 0;
	m_dBubble_move = 0;
	m_dCompare_number = 1;
	m_dDirect_com = 0;
	m_dDirect_move = 0;
	m_dHier_com = 0;
	m_dHier_move = 0;
	m_dPile_com = 0;
	m_dPile_move = 0;
	m_dQuick_com = 0;
	m_dQuick_move = 0;
	m_dSimple_com = 0;
	m_dSimple_move = 0;
	m_dView = _T("");
	m_dView1 = _T("");
	m_dView2 = _T("");
	m_dView3 = _T("");
	Quick_com=0;
	Quick_move=0;
	m_dOutput = 1;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CSort_compareDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CSort_compareDlg)
	DDX_Text(pDX, IDC_BUBBLE_COM, m_dBubble_com);
	DDX_Text(pDX, IDC_BUBBLE_MOVE, m_dBubble_move);
	DDX_Text(pDX, IDC_COMPARE_NUMBER, m_dCompare_number);
	DDX_Text(pDX, IDC_DIRECET_COM, m_dDirect_com);
	DDX_Text(pDX, IDC_DIRECT_MOVE, m_dDirect_move);
	DDX_Text(pDX, IDC_HIER_COM, m_dHier_com);
	DDX_Text(pDX, IDC_HIER_MOVE, m_dHier_move);
	DDX_Text(pDX, IDC_PILE_COM, m_dPile_com);
	DDX_Text(pDX, IDC_PILE_MOVE, m_dPile_move);
	DDX_Text(pDX, IDC_QUICK_COM, m_dQuick_com);
	DDX_Text(pDX, IDC_QUICK_MOVE, m_dQuick_move);
	DDX_Text(pDX, IDC_SIMPLE_COM, m_dSimple_com);
	DDX_Text(pDX, IDC_SIMPLE_MOVE, m_dSimple_move);
	DDX_Text(pDX, IDC_RICHEDIT, m_dView);
	DDX_Text(pDX, IDC_RICHEDIT1, m_dView1);
	DDX_Text(pDX, IDC_RICHEDIT2, m_dView2);
	DDX_Text(pDX, IDC_RICHEDIT3, m_dView3);
	DDX_Text(pDX, IDC_OUTPUT, m_dOutput);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CSort_compareDlg, CDialog)
	//{{AFX_MSG_MAP(CSort_compareDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_START_COMPARE, OnStartCompare)
	ON_BN_CLICKED(IDC_BUTTON1, OnOutput)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CSort_compareDlg message handlers

BOOL CSort_compareDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CSort_compareDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CSort_compareDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CSort_compareDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CSort_compareDlg::OnStartCompare() 
{
	this->UpdateData(true);
	int temp,i,j,m;
	int com,move;
	com=0;
	move=0;
	m=m_dCompare_number;
	m_dBubble_com=0;
	m_dBubble_move=0;
	m_dDirect_com=0;
	m_dDirect_move=0;
	m_dPile_com=0;
	m_dPile_move=0;
	m_dQuick_com=0;
	m_dQuick_move=0;
	m_dSimple_com=0;
	m_dSimple_move=0;
	m_dHier_com=0;
	m_dHier_move=0;
	for(m;m>=1;m--){//产生随机数，并赋给数组
	srand( (unsigned)time( NULL ) );
	for(i=1;i<=100;i++){
	temp=rand(); 
	temp=temp%99+1;
	array1[i]=temp;
	}
	for(i=1;i<=100;i++){
		array2[i]=array1[i];
		array3[i]=array1[i];
		array4[i]=array1[i];
		array5[i]=array1[i];
		array6[i]=array1[i];
	}
//冒泡排序法
	for(i=1;i<=100;i++){              
		for(j=i;j<=100;j++)
		{
			if(array1[j]<array1[i]){
				move++;
				temp=array1[j];
				array1[j]=array1[i];
				array1[i]=temp;
			}
			com++;
		}
	}
		m_dBubble_com=m_dBubble_com+com;
		m_dBubble_move=m_dBubble_move+move;
//冒泡排序法
int k=0;
com=0;
move=0;
//直接插入法

	for(i=2;i<=100;i++){
		for(j=0;j<=i;j++){
			com++;
			if(array2[i]<array2[j]){
			temp=array2[i];
			for(k=i;k>j;k--){
			move++;
			array2[k]=array2[k-1];
			}
			array2[j]=temp;
			break;
			}
		}
		}
	m_dDirect_com=m_dDirect_com+com;
	m_dDirect_move=m_dDirect_move+move;
//直接插入法
	com=0;
	move=0;
//快速排序法

CSort_compareDlg::QuickSort(array3,1,100);
m_dQuick_com=m_dQuick_com+Quick_com;
m_dQuick_move=m_dQuick_move+Quick_move;
//快速排序法
Quick_com=0;
Quick_move=0;
int min=0;
//简单选择法
for(i=1;i<=100;i++){
	temp=array4[i];
	for(j=i;j<=100;j++){
		com++;
		if(array4[j]<=temp){
			temp=array4[j];
			min=j;}
	}
	move++;
	temp=array4[i];
	array4[i]=array4[min];
	array4[min]=temp;
}
m_dSimple_com=m_dSimple_com+com;
m_dSimple_move=m_dSimple_move+move;
com=0;
move=0;
//简单选择法
//希尔排序法
int dlk[7];
dlk[0]=33;
dlk[1]=17;
dlk[2]=9;
dlk[3]=5;
dlk[4]=3;
dlk[5]=2;
dlk[6]=1;
for(i=0;i<=6;i++)
CSort_compareDlg::ShellInsert(array5,dlk[i]);
m_dHier_com=m_dHier_com+Quick_com;
m_dHier_move=m_dHier_move+Quick_move;
Quick_com=0;
Quick_move=0;
//堆法

for(i=50;i>=1;--i)
CSort_compareDlg::HeapAdjust(array6,1,100);
for(i=100;i>1;--i){
	temp=array6[1];
	Quick_move++;
	array6[1]=array6[i];
	array6[i]=temp;
CSort_compareDlg::HeapAdjust(array6,1,i-1);
}
m_dPile_com=m_dPile_com+Quick_com;
m_dPile_move=m_dPile_move+Quick_move;
Quick_com=0;
Quick_move=0;
//堆法
}
	m_dBubble_com=m_dBubble_com/m_dCompare_number;
	m_dBubble_move=m_dBubble_move/m_dCompare_number;
	m_dDirect_com=m_dDirect_com/m_dCompare_number;
	m_dDirect_move=m_dDirect_move/m_dCompare_number;
	m_dPile_com=m_dPile_com/m_dCompare_number;
	m_dPile_move=m_dPile_move/m_dCompare_number;
	m_dQuick_com=m_dQuick_com/m_dCompare_number;
	m_dQuick_move=m_dQuick_move/m_dCompare_number;
	m_dSimple_com=m_dSimple_com/m_dCompare_number;
	m_dSimple_move=m_dSimple_move/m_dCompare_number;
	m_dHier_com=m_dHier_com/m_dCompare_number;
	m_dHier_move=m_dHier_move/m_dCompare_number;
CString str;
switch(m_dOutput){
case 1:
str="冒泡排序法结果: ";
CSort_compareDlg::ArrayOutput(array1,str);
break;
case 2:
str="直接插入法结果: ";
CSort_compareDlg::ArrayOutput(array2,str);
break;
case 3:
str="简单选择法结果: ";
CSort_compareDlg::ArrayOutput(array4,str);
break;
case 4:
str="希尔法结果: ";
CSort_compareDlg::ArrayOutput(array5,str);
break;
case 5:
str="快速法结果: ";
CSort_compareDlg::ArrayOutput(array3,str);
break;
case 6:
str="堆法结果: ";
CSort_compareDlg::ArrayOutput(array6,str);
break;
}


	this->UpdateData(false);
}





void CSort_compareDlg::QuickSort(int *array, int low, int high)
{
	int pivotloc=0;
	if(low<high){
		pivotloc=CSort_compareDlg::Partition(array,low,high);
		CSort_compareDlg::QuickSort(array,low,pivotloc-1);
		CSort_compareDlg::QuickSort(array,pivotloc+1,high);
	}
}

int CSort_compareDlg::Partition(int *array, int low, int high)
{
int key=0,temp=0;
key=*(array+low);
while(low<high){
	while(low<high&&*(array+high)>=key){
		--high;
		Quick_com++;
	}
	Quick_com++;
	Quick_move++;
	temp=*(array+low);
	*(array+low)=*(array+high);
	*(array+high)=temp;
	
	while(low<high&&*(array+low)<=key){
		Quick_com++;
		++low;
	}
	Quick_com++;
	Quick_move++;
	temp=*(array+low);
	*(array+low)=*(array+high);
	*(array+high)=temp;
}
	return low;
	
}

void CSort_compareDlg::ShellInsert(int *array, int dk)
{
	int i=0,temp=0,j=0;
	for(i=dk+1;i<=100;++i){
		Quick_com++;
		if(array[i]<array[i-dk]){
		temp=array[i];
		for(j=i-dk;j>0&&(temp<array[j]);j-=dk){
		Quick_com++;
		Quick_move++;
		array[j+dk]=array[j];
		array[j]=temp;
		}
		}
	}
}

void CSort_compareDlg::HeapAdjust(int *array, int low, int high)
{
int temp,j;
temp=array[low];
for(j=2*low;j<=high;j*=2){
	Quick_com++;
	if(j<high&&(array[j]<array[j+1]))++j;
	Quick_com++;
	if(!(temp<array[j]))break;
	Quick_move++;
	array[low]=array[j];
	low=j;
}
array[low]=temp;
}



void CSort_compareDlg::ArrayOutput(int *array, CString str)
{
int i;
CString str1,str2;
for(i=1;i<=25;i++){
	str1.Format(_T("%d "),array[i]);
	str2=str2+str1;
	
}
m_dView=str+str2;
str2="               ";
for(i=26;i<=50;i++){
str1.Format(_T("%d "),array[i]);
	str2=str2+str1;
}
m_dView1=str2;
str2="               ";
for(i=51;i<=75;i++){
str1.Format(_T("%d "),array[i]);
	str2=str2+str1;
}
m_dView2=str2;
str2="               ";
for(i=76;i<=100;i++){
str1.Format(_T("%d "),array[i]);
	str2=str2+str1;
}
m_dView3=str2;
}

void CSort_compareDlg::OnOutput() 
{
	this->UpdateData(true);
	CString str;
switch(m_dOutput){
case 1:
str="冒泡排序法结果: ";
CSort_compareDlg::ArrayOutput(array1,str);
break;
case 2:
str="直接插入法结果: ";
CSort_compareDlg::ArrayOutput(array2,str);
break;
case 3:
str="简单选择法结果: ";
CSort_compareDlg::ArrayOutput(array4,str);
break;
case 4:
str="希尔法结果: ";
CSort_compareDlg::ArrayOutput(array5,str);
break;
case 5:
str="快速法结果: ";
CSort_compareDlg::ArrayOutput(array3,str);
break;
case 6:
str="堆法结果:";
CSort_compareDlg::ArrayOutput(array5,str);
break;
}
this->UpdateData(false);
}