sortview.cpp

数据结构与算法的排序算法演示,这是我上大学的时候做的实验,里面展示了几种常用的排序算法的算法演示,如插入排序,选择排序,快速排序,堆排序.

			}
	}
	m_IsRun=0;
}

//***************************************************************************//

void CSortView::Filter(int i,int n)//--------------------------筛选函数
{
	int j;
	pdata[0]->key=pdata[i]->key;
	HeapSortShow(0,i,1);
	j=2*i;
	showij(i,j);
	while(j<=n)
	{
		if((j<n)&&(pdata[j]->key<pdata[j+1]->key))
		{
			HeapSortShow(j,j+1,1);
			HeapSortShow(j,j+1,2);
			j++;
			showij(i,j);	
		}
        HeapSortShow(j,j/2,1);
		HeapSortShow(j,j/2,2);
		if(pdata[0]->key<pdata[j]->key)
		{
			pdata[i]->key=pdata[j]->key;
			pdata[j]->key=pdata[0]->key;
			HeapSortShow(i,j,1);
			HeapSortShow(i,j,2);
			i=j;
			j=2*i;
			showij(i,j);
		}
		else break;
	}
	pdata[i]->key=pdata[0]->key;
	HeapSortShow(0,i,2);
}


void CSortView::HeapSort(int n)//----------------------------堆排序
{
	m_IsRun=1;
	int i;
	for(i=n/2;i>=1;i--)
		Filter(i,n);
	for(i=n;i>1;i--)
	{
		pdata[0]->key=pdata[1]->key;
		pdata[1]->key=pdata[i]->key;
		pdata[i]->key=pdata[0]->key;
		HeapSortShow(1,i,3);
		Filter(1,i-1);
	}
	HeapSortShow(1,i,3);
	m_IsRun=0;
}

//***************************************************************************//

int CSortView::QuickPass(int low,int high)//-----------------一趟快速排序
{
	int down,up;
	down=low;
	up=high;
    pdata[0]->key=pdata[down]->key;
	QuickPassShow(up,down,3);
	showij(down,up);
	while(down<up)
	{
		while((down<up)&&(pdata[up]->key>=pdata[0]->key))
		{
			up--;
			QuickPassShow(up,up+1,1);
			showij(down,up);
		}
		if(down<up)
		{
			pdata[down]->key=pdata[up]->key;
			down++;
			QuickPassShow(down,down-1,1);
			showij(down,up);
		}
		while((down<up)&&(pdata[down]->key<=pdata[0]->key))
		{
			down++;
			QuickPassShow(down,down-1,1);
			showij(down,up);
		}
		if(down<up)
		{
			pdata[up]->key=pdata[down]->key;
			up--;
			QuickPassShow(up,up+1,1);
			showij(down,up);
		}
	}
	pdata[down]->key=pdata[0]->key;
	QuickPassShow(0,down,2);
	return down;
}

void CSortView::QuickSort(int low,int high)//------------------快速排序
{
	m_IsRun=1;
	int mid;
	if(low<high)
	{
		mid=QuickPass(low,high);
		QuickSort(low,mid-1);
		QuickSort(mid+1,high);
	}
	m_IsRun=0;
}

//*********************************************************************归并排序
void CSortView::Merge(int a[],int T[],int low,int mid,int high)//归并排序过程
{
	int i,j,k;
	i=low;j=mid+1;k=low;
	while((i<=mid)&&(j<=high))
		if(a[i]<=a[j])
			T[k++]=a[i++];
		else
			T[k++]=a[j++];
		while(i<=mid)
			T[k++]=a[i++];
		while(j<=high)
			T[k++]=a[j++];
}

void CSortView::MergePass(int a[],int T[],int length,int n)//合并数组
{
	int low,j;
	low=1;
	while(low+2*length-1<=n)
	{
		Merge(a,T,low,low+length-1,low+2*length-1);
		low=low+2*length;
	}
	if(low+length-1<n)
		Merge(a,T,low,low+length-1,n);
	else
		for(j=low;j<=n;j++)
			T[j]=a[j];
}

void CSortView::MergeSort(int a[],int n)
{
	int length;
	int *T=new int[n+1];
	length=1;
	while(length<n)
	{
		MergePass(a,T,length,n);
		length=2*length;
		MergePass(T,a,length,n);
		length=2*length;
	}
	delete T;
}

//***************************************************************************//
UINT MySort(LPVOID pParam)//--------------------------------线程函数
{
	CSortView* sort=(CSortView*)pParam;
	switch(Flag)
	{
	case 1:
		sort->InsertionSort();
		break;
	case 2:
		sort->BubbleSort();
		break;
	case 3:
		sort->SelectionSort();
		break;
	case 4:
		sort->QuickSort(1,sort->n);
		break;
	case 5:
		sort->HeapSort(sort->n);
		break;
	}
	return 0;
}

//***************************************************************************//命令相应函数

//***************************************************************************//输入
void CSortView::OnAutoinput() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	m_edit1.SetWindowText("");
	m_edit2.SetWindowText("");
	Flag=0;
	DrawType=1;
	AutoInput();
	Invalidate();
}

//***************************************************************************//
void CSortView::OnHeapinput() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	m_edit1.SetWindowText("");
	m_edit2.SetWindowText("");
	DrawType=2;
	AutoInput();
	Invalidate();
}

//***************************************************************************//排序
void CSortView::OnInsertionsort() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	if(DrawType==2)
	{
		MessageBox("请正确输入排序数据!");
		return;
	}
	Flag=1;
	CClientDC dc(this);
	dc.SetTextColor(RGB(0,0,255));
	dc.TextOut(400,30,"插入排序                    ");
	AfxBeginThread(MySort,(LPVOID)this);
}

//***************************************************************************//
void CSortView::OnBubblesort() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	if(DrawType==2)
	{
		MessageBox("请正确输入排序数据!");
		return;
	}
	Flag=2;
	CClientDC dc(this);
	dc.SetTextColor(RGB(0,0,255));
	dc.TextOut(400,30,"冒泡排序                   ");
	AfxBeginThread(MySort,(LPVOID)this);
}

//***************************************************************************//
void CSortView::OnSelectionsort() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	if(DrawType==2)
	{
		MessageBox("请正确输入排序数据!");
		return;
	}
	Flag=3;
	CClientDC dc(this);
	dc.SetTextColor(RGB(0,0,255));
	dc.TextOut(400,30,"选择排序                   ");
	AfxBeginThread(MySort,(LPVOID)this);
}

//***************************************************************************// 
void CSortView::OnQuicksort() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	if(DrawType==2)
	{
		MessageBox("请正确输入排序数据!");
		return;
	}
	Flag=4;
	CClientDC dc(this);
	dc.SetTextColor(RGB(0,0,255));
	dc.TextOut(400,30,"快速排序                   ");
	AfxBeginThread(MySort,(LPVOID)this);
}

//***************************************************************************//
void CSortView::OnHeapsort() 
{
	// TODO: Add your command handler code here
	if(m_IsRun==1)
	{
		MessageBox("排序正在执行中,请稍后!");
		return;
	}
	if(DrawType==1)
	{
		MessageBox("请正确输入排序数据!");
		return;
	}
	Flag=5;
	CClientDC dc(this);
	dc.SetTextColor(RGB(0,0,255));
	dc.TextOut(400,30,"堆排序                    ");
	AfxBeginThread(MySort,(LPVOID)this);
}

//***************************************************************************//创建ij显示EDit
int CSortView::OnCreate(LPCREATESTRUCT lpCreateStruct) 
{
	if (CView::OnCreate(lpCreateStruct) == -1)
		return -1;
	
	// TODO: Add your specialized creation code here
	m_edit1.Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_READONLY,CRect(100,80,130,100),this,1);
	m_edit2.Create(WS_CHILD|WS_VISIBLE|WS_BORDER|ES_READONLY,CRect(190,80,220,100),this,1);
	return 0;
}

//***************************************************************************//显示ij
void CSortView::showij(int i,int j)
{
	CString str;
	str.Format("%d",i);
	m_edit1.SetWindowText(str);
	str.Format("%d",j);
	m_edit2.SetWindowText(str);
}

//***************************************************************************//堆排序数据变换
void CSortView::HeapSortShow(int i,int j,int flag)
{
	CClientDC dc(this);
	Delay(400);
	switch(flag)
	{
	case 1:
		pdata[i]->SetColor(RGB(0,255,0),RGB(0,0,255));
		pdata[i]->DrawFace(&dc);
		pdata[j]->SetColor(RGB(0,255,0),RGB(0,0,255));
		pdata[j]->DrawFace(&dc);
		break;
	case 2:
		pdata[i]->SetColor(RGB(255,0,255),RGB(0,0,255));
		pdata[i]->DrawFace(&dc);
	    pdata[j]->SetColor(RGB(255,0,255),RGB(0,0,255));
	 	pdata[j]->DrawFace(&dc);
		break;
	case 3:
		pdata[i]->SetColor(RGB(255,0,255),RGB(0,0,255));
		pdata[i]->DrawFace(&dc);
		pdata[j]->SetColor(RGB(0,255,255),RGB(0,0,255));
		pdata[j]->DrawFace(&dc);
		break;
	}
}
///////////////////////////////////////////////////////////////////////////////////////////