quicksort.cpp

来自「包含八种排序算法的界面演示多线程程序,以线段形式表示数据大小,排序一清二楚」· C++ 代码 · 共 66 行

// QuickSort.cpp: implementation of the CQuickSort class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "sort.h"
#include "QuickSort.h"

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

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CQuickSort::CQuickSort()
{
	name=_TEXT("快速");
}

CQuickSort::~CQuickSort()
{

}

void CQuickSort::Sort()
{

	if (!IsCreated) return;
	if (SortHelper(0,n-1)) State2=2;
}

int CQuickSort::partition(int l, int r, int privot)
{
	int nn=r;
	int start=l;
	do
	{
		while (l<nn&&p[l]<=privot) {l++;if (State2==-1) {State2=1;return -2;}if (CanSleep) Sleep();}
		while (r!=start&&p[r]>=privot) {r--;if (State2==-1) {State2=1;return -2;}if (CanSleep) Sleep();}
		int temp=p[l];
		p[l]=p[r];
		p[r]=temp;
	}while(l<r);
	int temp=p[l];
	p[l]=p[r];
	p[r]=temp;
	return l;
}

BOOL CQuickSort::SortHelper(int l, int r)
{
	if (r<=l) return TRUE;
	int mid=partition(l,r,p[r]);
	int temp=p[r];
	p[r]=p[mid];
	p[mid]=temp;
	if (mid==-2) return FALSE;
	if (!SortHelper(l,mid-1)) return FALSE;
	if (!SortHelper(mid+1,r)) return FALSE;
	return TRUE;
}