sortdemodlg.cpp

采用MFC界面

// sortdemoDlg.cpp : implementation file
//

#include "stdafx.h"
#include "sortdemo.h"
#include "sortdemoDlg.h"
#include "math.h"
#include <fstream.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()
};
CDWordArray g_sortArray;
CDWordArray g_sortArray_Bubble;
DWORD *g_arrayQuick;
DWORD *g_arrayMerge;
DWORD *g_arrayHeap;
DWORD *g_arrayShell;
UINT g_NumCount;
UINT g_BubbleCount;
UINT g_ShellCount;
UINT g_QuickCount;
UINT g_MergeCount;
UINT g_HeapCount;
int g_bFlag[5];//设置线程中分配的内存是否需要释放
BOOL g_bIsSave;
int t;//希尔排序的趟数
int g_nCompleteCount=0;
//冒泡排序线程
//##########################################################
DWORD WINAPI ThreadProc_Bubble(LPVOID lpParameter)
{	
	CSortdemoDlg *pSortdemoDlg=(CSortdemoDlg*)lpParameter;
	
	UINT t1=SetTimer(pSortdemoDlg->m_hWnd,1,1,NULL);
	BOOL nFlag=FALSE;
	int length=::g_sortArray_Bubble.GetSize();
	for(int i=0;i<length-1;i++)
	{	
		g_BubbleCount=i+1;
		for(int j=0;j<length-1-i;j++)
		{	
			if(g_nCompleteCount>5)
				::ExitThread(0);//检测外部值，以便随时结束线程。
			if(g_sortArray_Bubble[j]>g_sortArray_Bubble[j+1])
			{
				DWORD temp;
				temp=g_sortArray_Bubble[j];
				g_sortArray_Bubble[j]=g_sortArray_Bubble[j+1];
				g_sortArray_Bubble[j+1]=temp;
				nFlag=TRUE;
			}
			
		}
		if (nFlag==FALSE)break;
	}
	g_BubbleCount++;
////////////////////////////////////////////////////保存结果
	if(g_bIsSave)
	{
		ofstream  f1("data_Bubble.txt",ios::binary);
		for(DWORD x=0;x<::g_BubbleCount;x++)
			if(x!=g_BubbleCount-1)
				f1<<::g_sortArray_Bubble[x]<<',';
			else
				f1<<::g_sortArray_Bubble[x];
		f1.close();
	}
///////////////////////////////////////////////////////////
	::g_sortArray_Bubble.RemoveAll();
	::g_bFlag[0]=1;
	CListBox*pLB=(CListBox*)pSortdemoDlg->GetDlgItem(IDC_LIST_INFO);
	int index;
	if(g_bIsSave)
		index=pLB->AddString(">>>>>>>冒泡排序已完成！结果保存在data_Bubble.txt中");
	else
		index=pLB->AddString(">>>>>>>冒泡排序已完成！");
	pLB->SetCurSel(index);
	Sleep(1000);
	KillTimer(pSortdemoDlg->m_hWnd,1);
	g_nCompleteCount++;//计算线程完成个数
	return 0;
}
//希尔排序线程
//##########################################################
void ShellInsert(DWORD a[],int length,int dk)
{
	for(int i=dk;i<length;++i)
	{	
		if(g_nCompleteCount>5)::ExitThread(0);//检测外部值，以便随时结束线程。
		if(a[i]<a[i-dk])
		{
			DWORD recKey=a[i];
			for(int j=i-dk;j>=0&&(recKey<a[j]);j-=dk)
				a[j+dk]=a[j];
			a[j+dk]=recKey;	
		}
	}
	
}
void ShellSort(DWORD a[],int n)
{
	t=(int)(log10(n+1)/log10(2));
	for(int k=1;k<=t;++k)
	{
		int dlta=(int)(pow(2,t-k+1)-1);
		ShellInsert(a,n,dlta);
		g_ShellCount++;
	}
}
DWORD WINAPI ThreadProc_Shell(LPVOID lpParameter)
{
	CSortdemoDlg *pSortdemoDlg=(CSortdemoDlg*)lpParameter;
	
	UINT t2=SetTimer(pSortdemoDlg->m_hWnd,2,1,NULL);
	int length=::g_NumCount;
	ShellSort(g_arrayShell,length);
//////////////////////////////////////////////保存结果到文件
	if(g_bIsSave)
	{
		ofstream  f1("data_Shell.txt",ios::binary);
		for(DWORD x=0;x<::g_NumCount;x++)
			if(x!=g_NumCount-1)
				f1<<::g_arrayShell[x]<<',';
			else
				f1<<::g_arrayShell[x];
		f1.close();
	}
///////////////////////////////////////////////////////////
	
	delete []g_arrayShell;//释放数组空间
	::g_bFlag[1]=1;
	CListBox*pLB=(CListBox*)pSortdemoDlg->GetDlgItem(IDC_LIST_INFO);
	int index;
	if(g_bIsSave)
		index=pLB->AddString(">>>>>>>希尔排序已完成！结果保存在data_Shell.txt中");
	else
		index=pLB->AddString(">>>>>>>希尔排序已完成！");
	pLB->SetCurSel(index);
	Sleep(1000);
	KillTimer(pSortdemoDlg->m_hWnd,2);
	g_nCompleteCount++;//计算线程完成个数
	return 0;

}
//快速排序线程
//##########################################################
DWORD partition(DWORD a[],DWORD low,DWORD high)
{
	DWORD privotkey=a[low];
	while(low<high)
	{
		if(g_nCompleteCount>5)::ExitThread(0);//检测外部值，以便随时结束线程。
		while(low<high&&a[high]>=privotkey)--high;
		a[low]=a[high];
		while(low<high&&a[low]<=privotkey)++low;
		a[high]=a[low];
	}
	a[low]=privotkey;
	::g_QuickCount++;
	return low;
}
void QSort(DWORD a[],DWORD low,DWORD high)
{
	if(low<high)
	{
		DWORD privotloc=partition(a,low,high);
		QSort(a,low,privotloc);
		QSort(a,privotloc+1,high);
	}
}
DWORD WINAPI ThreadProc_Quick(LPVOID lpParameter)
{
	CSortdemoDlg *pSortdemoDlg=(CSortdemoDlg*)lpParameter;
	UINT t3=SetTimer(pSortdemoDlg->m_hWnd,3,1,NULL);
	int length=g_NumCount;
	QSort(g_arrayQuick,0,length);
///////////////////////////////////////////////保存结果到文件
	if(g_bIsSave)
	{
		ofstream  f1("data_Quick.txt",ios::binary);
		for(DWORD x=0;x<::g_QuickCount;x++)
			if(x!=g_QuickCount-1)
				f1<<::g_arrayQuick[x]<<',';
			else
				f1<<::g_arrayQuick[x];
		f1.close();
	}
///////////////////////////////////////////////////////////
	delete []g_arrayQuick;//释放数组空间
	::g_bFlag[2]=1;
	CListBox*pLB=(CListBox*)pSortdemoDlg->GetDlgItem(IDC_LIST_INFO);
	int index;
	if(g_bIsSave)
		index=pLB->AddString(">>>>>>>快速排序已完成！结果保存在data_Quick.txt中");
	else
		index=pLB->AddString(">>>>>>>快速排序已完成！");
	pLB->SetCurSel(index);

	Sleep(1000);
	KillTimer(pSortdemoDlg->m_hWnd,3);
	g_nCompleteCount++;//计算线程完成个数
	return 0;

}
//##########################################################
//归并排序线程
void Merge(DWORD SR[],DWORD TR[],int i,int m,int n)
{
	int j,k;
	if(g_nCompleteCount>5)
		::ExitThread(0);//检测外部值，以便随时结束线程。
	for(j=m+1,k=i;i<=m && j<=n;k++)
		if(SR[i]<SR[j])
			TR[k]=SR[i++];
		else	
			TR[k]=SR[j++];
	if(i<=m)
	{
		while(i<=m)
			TR[k++]=SR[i++];
	}
	if(j<=n)
	{
		while(j<=n)
			TR[k++]=SR[j++];
	}
	::g_MergeCount++;
}
void MSort(DWORD SR[],DWORD TR1[],int s,int t)
{
	int m;
	DWORD *TR2=new DWORD[g_NumCount];
	ZeroMemory(TR2,g_NumCount*sizeof(DWORD));
	if(s==t)
		TR1[s]=SR[s];
	else
	{
		m=(s+t)/2;
		MSort(SR,TR2,s,m);
		MSort(SR,TR2,m+1,t);
		Merge(TR2,TR1,s,m,t);
	}
	delete []TR2;
}
DWORD WINAPI ThreadProc_Merge(LPVOID lpParameter)
{
	
	CSortdemoDlg *pSortdemoDlg=(CSortdemoDlg*)lpParameter;
	UINT t4=SetTimer(pSortdemoDlg->m_hWnd,4,1,NULL);
	int length=g_NumCount;
	MSort(g_arrayMerge,g_arrayMerge,0,length-1);
	g_MergeCount++;
//////////////////////////////////////////////保存结果到文件
	if(g_bIsSave)
	{
		ofstream  f1("data_Merge.txt",ios::binary);
		for(int x=0;x<length;x++)
			if(x!=length-1)
				f1<<::g_arrayMerge[x]<<',';
			else
				f1<<::g_arrayMerge[x];
		f1.close();
	}
///////////////////////////////////////////////////////////
	
	delete []g_arrayMerge;
	::g_bFlag[3]=1;
//	delete []TR2;
	CListBox*pLB=(CListBox*)pSortdemoDlg->GetDlgItem(IDC_LIST_INFO);
	int index;
	if(g_bIsSave)
		index=pLB->AddString(">>>>>>>归并排序已完成！结果保存在data_Merge.txt中");
	else
		index=pLB->AddString(">>>>>>>归并排序已完成！");
	pLB->SetCurSel(index);
	Sleep(1000);
	KillTimer(pSortdemoDlg->m_hWnd,4);
	g_nCompleteCount++;//计算线程完成个数
	return 0;
}
//堆排序线程
//##########################################################
void HeapAdjust(DWORD H[],int s,int m)//调整堆
{
	DWORD rc=H[s];
	if(g_nCompleteCount>5)::ExitThread(0);//检测外部值，以便随时结束线程。
	for(int j=2*s;j<=m;j*=2)
	{
		if(j<m&&(H[j]<H[j+1]))
			++j;
		if(rc> H[j])
			break;
		H[s]=H[j];
		s=j;
	}
	H[s]=rc;
}
void HeapSort(DWORD H[],int length)//筛选堆
{
	for(int i=length/2;i>0;--i)
		HeapAdjust(H,i,length);
	for(i=length;i>1;--i)
	{
		DWORD temp=H[1];
		H[1]=H[i];
		H[i]=temp;
		HeapAdjust(H,1,i-1);
		::g_HeapCount++;
	}
}
DWORD WINAPI ThreadProc_Heap(LPVOID lpParameter)
{
	CSortdemoDlg *pSortdemoDlg=(CSortdemoDlg*)lpParameter;
	UINT t5=SetTimer(pSortdemoDlg->m_hWnd,5,1,NULL);
	int length=g_NumCount;
	HeapSort(g_arrayHeap,length);
	g_HeapCount++;
///////////////////////////////////////////////保存结果到文件
	if(g_bIsSave)
	{
		ofstream  f1("data_Heap.txt",ios::binary);
		for(int x=1;x<=length;x++)
			if(x!=length)
				f1<<::g_arrayHeap[x]<<',';
			else
				f1<<::g_arrayHeap[x];
		f1.close();
	}
///////////////////////////////////////////////////////////
	delete []g_arrayHeap;
	::g_bFlag[4]=1;
	CListBox*pLB=(CListBox*)pSortdemoDlg->GetDlgItem(IDC_LIST_INFO);
	int index;
	if(g_bIsSave)
		index=pLB->AddString(">>>>>>>堆排序已完成！结果保存在data_Heap.txt中");
	else