quicksort.cpp

内存映射

// QuickSort.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "stdlib.h"
#include "memory.h"
#include <iostream.h>
#define MAX_THREAD_NO 20 // 控制产生的最大线程数在20个
#define MIN_DATA_NO 1000 //处理的数据小于1000以后不再分割


//下面的结构是用于主线程与子线程通信
struct LHIndex//快速排序用
{
	unsigned long lIndex;//低指针
	unsigned long hIndex;//高指针
	unsigned long TID; //线程ID
};

LHIndex *pLHIndex;
static long curThreadNO = 0 ;
   

HANDLE evtNotFull;//事件信号,标记当前子线程数是否 < MAX_THREAD_NO
HANDLE evtCompleted;   //事件信号,标记事件是否已完成全部线程

//CRITICAL_SECTION csPrint;   //临界区
HANDLE mtxNewLHIndex; //互斥信号,如有信号表明已经有线程进入临界区并拥有此信号
HANDLE mtxNewThread;
HANDLE mtxScreenPrint;
int *Array = NULL;
static char filepath[]="random.txt1"; 
unsigned long __stdcall QuickSort(void* lhIndex);  //快速排序
void HeapSort(int lLow,int lHigh );
void StartQuickSort(int lLow,int lHigh);
void sort(int l,int h );
int main(int argc, char* argv[])
{

//初始化地址//
	char modulepath[MAX_PATH];
	GetModuleFileName(NULL,modulepath,MAX_PATH);
	char *pdest = strrchr(modulepath,'\\');
	strncpy(pdest+1,filepath,sizeof(filepath));	
	//////////////////////////////////////////////////////////////////////////
//初始化内存映射//
	HANDLE hFile = CreateFile(modulepath,GENERIC_WRITE|GENERIC_READ,0,NULL
		,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL);
	if(hFile == INVALID_HANDLE_VALUE)
	{
		printf("File could not be opened.");
		return FALSE;
	}
	
	DWORD dwFileSize = GetFileSize(hFile,NULL);	
	HANDLE hFileMap = CreateFileMapping(hFile,NULL,PAGE_READWRITE,0,
		dwFileSize,NULL);
	
	if(hFileMap == NULL){
		CloseHandle(hFile);
		return FALSE;
	}
	Array = (int *)MapViewOfFile(hFileMap,FILE_MAP_WRITE,0,0,0);
	
	if(Array == NULL){
		CloseHandle(hFileMap);
		CloseHandle(hFile);
		return FALSE;
	}
//////////////////////////////////////////////////////////////////////////
	//对信号量进行初始化
	evtCompleted = CreateEvent(NULL, FALSE, FALSE, "Complete");
	mtxNewLHIndex = CreateMutex(NULL, FALSE, "NewLHIndex");
	mtxNewThread = CreateMutex(NULL, FALSE, "NewThread");
	mtxScreenPrint = CreateMutex(NULL, FALSE, "ScreenPrint");

	StartQuickSort(0,dwFileSize/sizeof(int)-1);
	
	WaitForSingleObject(evtCompleted,INFINITE);	
	//////////////////////////////////////////////////////////////////////////
	//释放内存映射//	
	UnmapViewOfFile(Array);
	CloseHandle(hFileMap);	
	SetFilePointer(hFile,dwFileSize,NULL,FILE_BEGIN);
	//SetEndOfFile(hFile);//实际上不需要写入了。
	CloseHandle(hFile);	

	CloseHandle(evtCompleted);
	CloseHandle(mtxNewThread);
	CloseHandle(mtxNewLHIndex);
	CloseHandle(mtxScreenPrint);
	//退出
	cout<<"Exit :x/X "<<endl;
	char x;	
	do
	{
		cin>>x;
	}while( x!='x'&& x!='X');
	return 0;
}
void StartQuickSort(int lLow,int lHigh)
{
    WaitForSingleObject( mtxNewLHIndex, INFINITE );      
	pLHIndex = new LHIndex;	LHIndex *pLeftLHIndex = pLHIndex;
	pLeftLHIndex->hIndex = lHigh;
	pLeftLHIndex->lIndex =  lLow;		
	ReleaseMutex( mtxNewLHIndex );
	
	WaitForSingleObject( mtxNewThread, INFINITE );  
	curThreadNO++; 
	CreateThread(NULL, 0, &QuickSort, pLeftLHIndex, NULL, &pLeftLHIndex->TID);//left
	ReleaseMutex( mtxNewThread );
}
void sort(int l,int h )
{
	long lLow = l;
	long lHigh = h;  
	
	int lLowSaved = lLow, lHighSaved = lHigh;  //保未改变的lLow，lHigh值保存起来
	
	int pivot=Array[(lLow+lHigh)/2];
	int temp;
	while(lLow<lHigh)
	{
		while(Array[lLow]<pivot) ++lLow;
		while(Array[lHigh]>pivot) --lHigh;
		if(lLow>=lHigh) break;
		
		temp=Array[lLow];
		Array[lLow]=Array[lHigh];
		Array[lHigh]=temp;
		++lLow; --lHigh;		
	}
	if(lLow == lHigh) lLow++;
	if(lLowSaved < lHigh) sort(lLowSaved,lLow-1);
	if(lLow < lHighSaved) sort(lHigh+1,lHighSaved);

}
unsigned long __stdcall QuickSort(void* theLHIndex)
{
	long lLow = ((LHIndex*)theLHIndex)->lIndex;
	long lHigh = ((LHIndex*)theLHIndex)->hIndex;  
	int lLowSaved = lLow, lHighSaved = lHigh;  //保未改变的lLow，lHigh值保存起来

	unsigned long theID = ((LHIndex*)theLHIndex)->TID;	
	if(lLow >= lHigh)//递归结束条件
	{
		return 1L; 
		delete theLHIndex;
	}
    WaitForSingleObject( mtxScreenPrint, INFINITE );
 	cout <<"start quicksort. count : "<<curThreadNO<<"\tID: "<< theID <<"\tLow: "<<lLow<<"\tHigh: "<<lHigh<<endl;
	ReleaseMutex( mtxScreenPrint );

	int pivot=Array[(lLow+lHigh)/2];
	int temp;
	while(lLow<lHigh)
	{
		while(Array[lLow]<pivot) ++lLow;
		while(Array[lHigh]>pivot) --lHigh;
		if(lLow>=lHigh) break;
		
		temp=Array[lLow];
		Array[lLow]=Array[lHigh];
		Array[lHigh]=temp;
		++lLow; --lHigh;		
	}

	if(lLow == lHigh) lLow++;
	if(lLowSaved < lHigh) sort(lLowSaved,lLow-1);
	if(lLow < lHighSaved) sort(lHigh+1,lHighSaved);

	if(lLow == lHigh) lLow++;
	if(lLow - lLowSaved <= MIN_DATA_NO ) //处理的数据小于1000以后不再分割,用堆排序处理,也可用其它的排序方法
	{	
		if (lLowSaved < lLow-1)
		{
			HeapSort(lLowSaved,lLow-1 );
		}
	}
	else
	{		
		StartQuickSort(lLowSaved,lLow-1);		
	}
	//处理右边	
	if(lHighSaved - lHigh <= MIN_DATA_NO )  //处理的数据小于1000以后不再分割,用堆排序处理
	{
		if ( lHigh+1<= lHighSaved)
		{
			HeapSort(lHigh+1,lHighSaved );
		}
	}
	else
	{
		StartQuickSort(lHigh+1,lHighSaved);
	}
//////////////////////////////////////////////////////////////////////////
//本线程已基本执行完。
	WaitForSingleObject( mtxScreenPrint, INFINITE );
	cout <<"end quicksort thread. ID:"<< theID <<"\tLow: "<<lLowSaved<<"\tHigh: "<<lHighSaved<<endl;
	cout <<curThreadNO<<endl;
   	ReleaseMutex( mtxScreenPrint );	
//////////////////////////////////////////////////////////////////////////
	delete theLHIndex;	
	WaitForSingleObject( mtxNewThread, INFINITE );  
	curThreadNO--; 
	if( curThreadNO == 0)
		SetEvent(evtCompleted);//检查是否其他线程都已执行完	,当线程数为0时,既执行完成
	ReleaseMutex( mtxNewThread );

	return 1L;
}
//堆排序
void HeapSort(int lLow,int lHigh )
{
	int i, j, p;
	long swap;
    WaitForSingleObject( mtxScreenPrint, INFINITE );
	cout <<"start HeapSort"<<lLow<<"------"<<lHigh<<endl;
	ReleaseMutex( mtxScreenPrint );

	for(i = lLow; i < lHigh; i++)
	{
		for(j = lHigh ; j > i; j--) //从最后倒数上去比较字节点和父节点
		{
			p = (j - i - 1)/2 + i;   //计算父节点数组下标
			//注意到树节点序数跟数组下标不是等同的，因为建堆的元素个数逐个递减
			if(Array[j] < Array[p])  //如果父节点数值大则交换父节点和字节点
			{
				swap = Array[j];
				Array[j] = Array[p];
				Array[p] = swap;
			}
		}
	}
    WaitForSingleObject( mtxScreenPrint, INFINITE );
	cout <<"start HeapSort"<<lLow<<"------"<<lHigh<<endl;
	ReleaseMutex( mtxScreenPrint );
}