algorithmn1dlg.cpp

几种排序算法的VC++实现

// Algorithmn1Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "Algorithmn1.h"
#include "Algorithmn1Dlg.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()

/////////////////////////////////////////////////////////////////////////////
// CAlgorithmn1Dlg dialog

CAlgorithmn1Dlg::CAlgorithmn1Dlg(CWnd* pParent /*=NULL*/)
	: CDialog(CAlgorithmn1Dlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CAlgorithmn1Dlg)
	m_intInput = 0;
	m_intN = 0;
	m_Intselection = 0;
	m_intInsertion = 0;
	m_intBottomup = 0;
	m_intMerge = 0;
	m_intQuick = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
	enter=0;//用于记录数组大小
	num=0;//用于快速排序的计数
}

void CAlgorithmn1Dlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAlgorithmn1Dlg)
	DDX_Text(pDX, IDC_INPUT, m_intInput);
	DDX_Text(pDX, IDC_N, m_intN);
	DDX_Text(pDX, IDC_EDIT_SELECTIONSORT, m_Intselection);
	DDX_Text(pDX, IDC_EDIT_INSERTIONSORT, m_intInsertion);
	DDX_Text(pDX, IDC_EDIT_BOTTOMUPSORT, m_intBottomup);
	DDX_Text(pDX, IDC_EDIT_MERGESORT, m_intMerge);
	DDX_Text(pDX, IDC_EDIT_QUICKSORT, m_intQuick);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAlgorithmn1Dlg, CDialog)
	//{{AFX_MSG_MAP(CAlgorithmn1Dlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_SELECTIONSORT, OnSelectionsort)
	ON_BN_CLICKED(IDC_INSERTIONSORT, OnInsertionsort)
	ON_BN_CLICKED(IDC_BOTTOMUPSORT, OnBottomupsort)
	ON_BN_CLICKED(IDC_MERGESORT, OnMergesort)
	ON_BN_CLICKED(IDC_QUICKSORT, OnQuicksort)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CAlgorithmn1Dlg message handlers

BOOL CAlgorithmn1Dlg::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 CAlgorithmn1Dlg::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 CAlgorithmn1Dlg::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 CAlgorithmn1Dlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}


//数组产生
void CAlgorithmn1Dlg::OnOK() 
{
	// TODO: Add extra validation here
	UpdateData();	
	enter=m_intInput;
	srand((unsigned long)time(0));
	if(enter<=0)
	{
		MessageBox("输入正整数    ","友情提示",MB_ICONSTOP);
	}

	else if(enter>5000)
	{
		MessageBox("输入5000以内的数    ","友情提示",MB_ICONSTOP);
	}

	else
	{	
		array[0]=0;
		for(int i=1;i<=enter;++i)
		{
			array[i]=rand()%32768;		
		}
		m_intN=enter;
		m_Intselection=0;
		m_intInsertion=0;
		m_intBottomup=0;
		m_intMerge=0;
		m_intQuick=0;
	}
	
	UpdateData(FALSE);
}




//选择排序
int CAlgorithmn1Dlg::selection()
{
	int m=0;//记录比较次数
	
	int *array1=new int[enter+1];
	for(int i1=1;i1<=enter;++i1)
	{
		array1[i1]=array[i1];		
	}
	
	for(int i=1;i<=enter-1;++i)
	{
		int k=i;
		int a;
		for(int j=i+1;j<=enter;++j)
		{
			m+=1;
			if(array1[k]>array1[j])
				k=j;
		}
		if(k!=i)
		{
			a=array1[k];
			array1[k]=array1[i];
			array1[i]=a;
		}
	}

	delete []array1;
	return m;
}


void CAlgorithmn1Dlg::OnSelectionsort() 
{
	// TODO: Add your control notification handler code here
	UpdateData();
	int m=selection();
	m_Intselection=m;
	UpdateData(FALSE);
	
}




//插入排序
int CAlgorithmn1Dlg::insertion()
{
	int m=0;//记录比较次数

	int *array1=new int[enter+1];
	for(int i1=1;i1<=enter;++i1)
	{
		array1[i1]=array[i1];		
	}
	
	
	for(int i=2;i<=enter;++i)
	{
		int x=array1[i];
		int j=i-1;	
		
		while(j>0 && array1[j]>x)
		{
			array1[j+1]=array1[j];
			j=j-1;
			m+=1;
		}
		array1[j+1]=x;		
	}
	
    delete []array1;
	return m;
}

void CAlgorithmn1Dlg::OnInsertionsort() 
{
	// TODO: Add your control notification handler code here
	UpdateData();
	int m=insertion();
	m_intInsertion=m;
	UpdateData(FALSE);	
}



//自底向上归并排序
int CAlgorithmn1Dlg::merge(int *A,int p,int q,int r)
{
	//int a=r-p+1;
	int m=0;
	int *B=new int[r+1];
	int s=p;
	int t=q+1;
	int k=p;
	while(s<=q&&t<=r)
	{
		if(A[s]<=A[t])
		{
			B[k]=A[s];
			s=s+1;
		}
		else
		{
			B[k]=A[t];
			t=t+1;
		}
		k=k+1;
		m++;
	}
	if(s==q+1)
	{
		for(int i=0;i<=r-k;i++)
		{
			*(B+k+i)=*(A+t+i);
		}
	}
	else
	{
		for(int j=0;j<=r-k;j++)
		{
			*(B+s+j)=*(A+s+j);
		}
	}
	for(int b=0;b<=r-p;b++)
	{
		*(A+p+b)=*(B+p+b);		
	}
	delete B;
	return m;
}



int CAlgorithmn1Dlg::bottomup()
{
	int m=0;//记录比较次数

	int *array1=new int[enter+1];
	for(int i1=1;i1<=enter;++i1)
	{
		array1[i1]=array[i1];		
	}	
	
	int s;
	int i;
	int t=1;
	while (t<enter)
	{
		s=t;
		t=2*s;
		i=0;
		while(i+t<=enter)
		{
			m+=merge(array1,i+1,i+s,i+t);
			i=i+t;
		}
		if(i+s<enter)
			m+=merge(array1,i+1,i+s,enter);
	}
	return m;

}


void CAlgorithmn1Dlg::OnBottomupsort() 
{
	// TODO: Add your control notification handler code here
	UpdateData();
	int m=bottomup();
	m_intBottomup=m;
	UpdateData(FALSE);	
}



//归并排序
int CAlgorithmn1Dlg::mergesort(int *A,int low,int high)
{
	int m=0;
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		m+=mergesort(A,low,mid);
		m+=mergesort(A,mid+1,high);
		m+=merge(A,low,mid,high);
	}
	return m;
}



void CAlgorithmn1Dlg::OnMergesort() 
{
	// TODO: Add your control notification handler code here
	UpdateData();


	int *array1=new int[enter+1];
	for(int i1=1;i1<=enter;++i1)
	{
		array1[i1]=array[i1];		
	}		
	
	int m=mergesort(array1,1,enter);
	m_intMerge=m;
	UpdateData(FALSE);
	
}


//快速排序
int CAlgorithmn1Dlg::split(int *A,int low,int high)
{
	int i=low;
	int w;
	int a;
	
	int x=A[low];
	for(int j=low+1;j<=high;j++)
	{
		if(A[j]<=x)
		{
			i=i+1;
			if(j!=i)
			{
				a=A[i];
				A[i]=A[j];
				A[j]=a;
			}
		}
	}
	a=A[low];
	A[low]=A[i];
	A[i]=a;
	w=i;
	
	return w;
}


int CAlgorithmn1Dlg::quick(int *A,int low,int high)
{
	int w1;
	if(low<high)
	{   w1=split(A,low,high);				
		num+=high-low;
		quick(A,low,w1-1);
		quick(A,w1+1,high);
	}
    return 1;
}



void CAlgorithmn1Dlg::OnQuicksort() 
{
	// TODO: Add your control notification handler code here
	UpdateData();


	int *array1=new int[enter+1];
	for(int i1=1;i1<=enter;++i1)
	{
		array1[i1]=array[i1];		
	}		

	quick(array1,1,enter);	
	m_intQuick=num;

	num=0;
	UpdateData(FALSE);
	
}