快速排序算法view.cpp

快速排序算发,2分法查找,比一般的算发快,编译通过

// 快速排序算法View.cpp : implementation of the CMyView class
//

#include "stdafx.h"
#include "快速排序算法.h"

#include "快速排序算法Doc.h"
#include "快速排序算法View.h"

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

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

IMPLEMENT_DYNCREATE(CMyView, CView)

BEGIN_MESSAGE_MAP(CMyView, CView)
	//{{AFX_MSG_MAP(CMyView)
	ON_COMMAND(ID_MENUCOMPUTER, OnMenucomputer)
	//}}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::OnMenucomputer() 
{
	int data[] = {100001,100011,100012,100019,100018,100016,100002,100003,100004,100017,100005,100006,100007,100008,100015,100014,100013,100012,100000,100009,100010};  

	QuickSort(data,20);  	
	int b0 = find(data,100001,20);
	int b1 = find(data,100001,20);
	int b2 = find(data,100002,20);
	int b3 = find(data,100003,20);
	int b4 = find(data,100004,20);
	int b5 = find(data,100005,20);
	int b6 = find(data,100006,20);
	int b7 = find(data,100007,20);
	int b8 = find(data,100008,20);
	int b9 = find(data,100009,20);
	int b10 = find(data,100010,20);
	int b11 = find(data,100011,20);
	int b12 = find(data,100012,20);
	int b13 = find(data,100013,20);
	int b14 = find(data,100014,20);
	int b15 = find(data,100015,20);
	int b16 = find(data,100016,20);
	int b17 = find(data,100017,20);
	int b18 = find(data,100018,20);
	int b19 = find(data,100019,20);
}

void CMyView::QuickSort(int* pData,int Count)
{
	quickSort(pData,0,Count-1);
}

void CMyView::quickSort(int* pData,int left,int right)
{
	int i,j;  
	int middle,iTemp;  

	i = left;  
	j = right;  
	middle = pData[(left+right)/2]; //求中间值  
	do{  
		while((pData[i]<middle) && (i<right))//从左扫描大于中值的数  
			i++;       
		while((pData[j]>middle) && (j>left))//从右扫描大于中值的数  
			j--;  
		if(i<=j)//找到了一对值  
		{  
			//交换  
			iTemp = pData[i];  
	
			pData[i] = pData[j];  
			pData[j] = iTemp;  
			i++;  
			j--; 
		
		} 
	}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）  
	             //当左边部分有值(left<j)，递归左半边  
	if(left<j)  
		quickSort(pData,left,j);  
	             //当右边部分有值(right>i)，递归右半边  
	if(right>i)  
		quickSort(pData,i,right);  
}

int CMyView::find(int* pData , int a ,int total)
{
	int maxindex = total - 1;
	int minindex = 0;
    int midindex = 0 ;
	while(minindex <= maxindex){

        midindex = ( maxindex + minindex )/2;

		if( pData[midindex] < a){         
			minindex = midindex + 1;
		}
		else if( pData[minindex] > a){           
			maxindex = midindex - 1 ;
		}
        else {
		   return  midindex;
        }
   	} 
   return -1;
}