排序作业view.cpp

该程序里面是关于排序方面的肉容

// 排序作业View.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "排序作业.h"

#include "排序作业Doc.h"
#include "排序作业View.h"
#include "SuijichanshengDialog.h"
#include "shougongshurudialog.h"
#include "shifozaishurushuzu.h"
extern long *A,*B,*C;
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
int TEMP=2;
double dm[100],dq[100];
long n[100];
int temp;
long NN;
int I;

/////////////////////////////////////////////////////////////////////////////
// CMyView

IMPLEMENT_DYNCREATE(CMyView, CView)

BEGIN_MESSAGE_MAP(CMyView, CView)
	//{{AFX_MSG_MAP(CMyView)
	ON_COMMAND(ID_shuijichansheng, Onshuijichansheng)
	ON_COMMAND(ID_shougongchansheng, Onshougongchansheng)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyView construction/destruction

CMyView::CMyView()
{
	// TODO: add construction code here

}

CMyView::~CMyView()
{
}

BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CMyView drawing

void CMyView::OnDraw(CDC* pDC)
{
	CMyDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CMyView printing

BOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CMyView diagnostics

#ifdef _DEBUG
void CMyView::AssertValid() const
{
	CView::AssertValid();
}

void CMyView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CMyDoc* CMyView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));
	return (CMyDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMyView message handlers

void CMyView::MERGE(long low, long mid, long high)
{
long h,i,j,k;
  h=low;
  i=low;
  j=mid+1;
  while(h<=mid&&j<=high)
  {
     if(A[h]<=A[j])
     {
       B[i]=A[h];
       h++;
     }
     else
     {
       B[i]=A[j];
       j++;
     }
     i++;
   }
   if(h>mid)
     for(k=j;k<=high;k++)
       {
         B[i]=A[k];
         i++;
       }
   else
      for(k=h;k<=mid;k++)
       {
         B[i]=A[k];
         i++;
       }
   for(k=low;k<=high;k++)
       A[k]=B[k];

}

void CMyView::MERGESORT(long low, long high)
{ long mid;
   if(low<high)
     {
       mid=(long)((low+high)/2);
       MERGESORT(low,mid);   
       MERGESORT(mid+1,high);  
       MERGE(low,mid,high);   
     }


}


void CMyView::Onshuijichansheng() 
{

	
long i;
	for(int a=1;a<=20;a++)
	{n[a]=5000*a;}
	time_t t;
	int j;
	CDC *PDC=GetDC();
	POINT p1,p2;
	
	PDC->TextOut(100,10,"归并分类和快速分类时间比较表（时间单位毫秒）");
	double start,end;
    char *str;
	str=new char[11];
	for(j=1;j<=20;j++)
	{
	A=new long[n[j]+1];
	B=new long[n[j]+1];
	C=new long[n[j]+1];
    if(((j-1)%5)==0)
	   {
        p1.x=0;p1.y=25+((int)((j-1)/5))*70;
	     p2.x=600;p2.y=25+((int)((j-1)/5))*70;
	     PDC->MoveTo(p1);
	     PDC->LineTo(p2);
        PDC->TextOut(0,30+((int)((j-1)/5))*70,"元素个数");
	     PDC->TextOut(0,50+((int)((j-1)/5))*70,"归并分类");
	     PDC->TextOut(0,70+((int)((j-1)/5))*70,"快速分类");
	     p1.x=0;p1.y=25+((int)((j-1)/5)+1)*70;
	     p2.x=600;p2.y=25+((int)((j-1)/5)+1)*70;
	     PDC->MoveTo(p1);
	     PDC->LineTo(p2);
	   }

   srand(time(&t));
	for(i=1;i<=n[j];i++)
	{
	    A[i]=C[i]=rand()%100000;
    }
	
	PDC->TextOut(((j-1)%5+1)*100,30+((int)((j-1)/5))*70,ltoa(n[j],str,10));
  
    

	start=clock();
	MERGESORT(1,n[j]);
	end=clock();
	dm[j]=(end-start);
  	PDC->TextOut(((j-1)%5+1)*100,50+((int)((j-1)/5))*70,ltoa((long)dm[j],str,10));
	

	start=clock();
   QUICKSORT(1,n[j]);
	end=clock();
	dq[j]=(end-start);
   PDC->TextOut(((j-1)%5+1)*100,70+((int)((j-1)/5))*70,ltoa((long)dq[j],str,10));
	
   }
	

	// TODO: Add your command handler code here
	
}







long CMyView::PARTITION(long low, long high)
{
long down,up,temp;
	down=low;
	up=high;
	long j=MIDDLEINT(low,(low+high)/2,high);//返回其值居中间的元素下标
    temp=C[low];
	A[low]=C[j];
	A[j]=temp;
	long v=C[low];
	while(down<up)
	{
		while((down<up)&&(C[up]>=v))
			up--;
		if(down<up)
			C[down++]=C[up];
        while((down<up)&&(C[down]<=v))
			down++;
		if(down<up)
			C[up--]=C[down];
	}
	C[down]=v;
	return down;

}

long CMyView::MIDDLEINT(long x, long y, long z)
{
if(((C[x]<=C[y])&&(C[x]>=C[z]))||((C[x]<=C[z])&&(C[x]>=C[y])))
		return(x);
	if(((C[y]>=C[x])&&(C[y]<=C[z]))||((C[y]<=C[x])&&(C[y]>=C[z])))
		return(y);
	else 
		return(z);

}

void CMyView::QUICKSORT(long low, long high)
{long mid;
	if(low<high)
	{
  	  mid=PARTITION(low,high);
	  QUICKSORT(low,mid-1);
	  QUICKSORT(mid+1,high);
	}


}



void CMyView::Onshougongchansheng() 
{ 
	// TODO: Add your command handler code here
	
}