sequence.cpp

用多线程来排序,共有五种算法.

// sequence.cpp : Defines the entry point for the console application.
/*
主要用到的WINAPI线程控制函数，有关详细说明请查看MSDN

线程建立函数
HANDLE CreateThread(
  LPSECURITY_ATTRIBUTES lpThreadAttributes,  
  // 安全属性结构指针，可为NULL
  DWORD dwStackSize,                         
  // 线程栈大小，若为0表示使用默认值
  LPTHREAD_START_ROUTINE lpStartAddress,     
  // 指向线程函数的指针
  LPVOID lpParameter,                        
  // 传递给线程函数的参数，可以保存一个指针值
  //所以，线程函数的参数只能是一个32位值
  //而且线程函数返回值也有规定，必须是unsigned long
  DWORD dwCreationFlags,                     
  // 线程建立是的初始标记，运行或挂起
  LPDWORD lpThreadId                         
  // 指向接收线程号的DWORD变量
);
 
对临界资源控制的多线程控制的信号函数：
HANDLE CreateEvent(
  LPSECURITY_ATTRIBUTES lpEventAttributes,
                      // 安全属性结构指针，可为NULL
  BOOL bManualReset,  
  // 手动清除信号标记，TRUE在WaitForSingleObject后必须手动调
  //用RetEvent清除信号。
  //若为FALSE则在WaitForSingleObject后，系统自动清除事件信号
  BOOL bInitialState, // 初始状态，TRUE有信号，FALSE无信号
  LPCTSTR lpName      // 信号量的名称，字符数不可多于MAX_PATH
  //如果遇到同名的其他信号量函数就会失败，如果遇到同类信号同名
  //也要注意变化
);

HANDLE CreateMutex(
  LPSECURITY_ATTRIBUTES lpMutexAttributes,
                       // 安全属性结构指针，可为NULL
  BOOL bInitialOwner,  // 当前建立互斥量是否占有该互斥量
  //TRUE表示占有，这样其他线程就不能获得此互斥量也就无法进入由
  //该互斥量控制的临界区。FALSE表示不占有该互斥量
  LPCTSTR lpName       // 信号量的名称，字符数不可多于MAX_PATH
  //如果遇到同名的其他信号量函数就会失败，如果遇到同类信号同名
  //也要注意变化
);

//初始化临界区信号，使用前必须先初始化
VOID InitializeCriticalSection(
  LPCRITICAL_SECTION lpCriticalSection   // 临界区变量指针
);

//阻塞函数
//如果等待的信号量不可用，那么线程就会挂起，直到信号可用
//线程才会被唤醒，该函数会自动修改信号，如Event，线程被唤醒之后
//Event信号会变得无信号，Mutex、Semaphore等也会变。
DWORD WaitForSingleObject(
  HANDLE hHandle,        // 等待对象的句柄
  DWORD dwMilliseconds   // 等待毫秒数，INFINITE表示无限等待
);
//如果要等待多个信号可以使用WaitForMutipleObject函数
*/


#include "stdafx.h"
#include "stdlib.h"
#include "memory.h"

HANDLE evtTerminate; //事件信号,标记是否所有子线程都执行完

/*
下面使用了三种控制方法，你可以注释其中两种，使用其中一种。
注意修改时要连带修改临界区PrintResult里的相应控制语句
*/
HANDLE evtPrint;   //事件信号,标记事件是否已发生
//CRITICAL_SECTION csPrint;   //临界区
//HANDLE mtxPrint; //互斥信号,如有信号表明已经有线程进入临界区并拥有此信号

static long ThreadCompleted = 0;   
/*用来标记四个子线程中已完成线程的个数,
当一个子线程完成时就对ThreadCompleted进行加一操作, 
要使用InterlockedIncrement(long* lpAddend)和
InterlockedDecrement(long* lpAddend)进行加减操作
*/

//下面的结构是用于传送排序的数据给各个排序子线程
struct MySafeArray
{
	long* data;
	int iLength;
};

//打印每一个线程的排序结果
void PrintResult(long* Array, int iLength, const char* HeadStr = "sort");

//排序函数
unsigned long __stdcall BubbleSort(void* theArray);  //冒泡排序
unsigned long __stdcall SelectSort(void* theArray);  //选择排序
unsigned long __stdcall HeapSort(void* theArray);    //堆排序
unsigned long __stdcall InsertSort(void* theArray);  //插入排序
/*以上四个函数的声明必须乎合作为一个线程函数的必要条件才可以使用CreateThread
建立一个线程。
（1）调用方法必须是__stdcall，即函数参数压栈顺序由右到左，而且由函数本身负责
栈的恢复, C和C++默认是__cdecl, 所以要显式声明是__stdcall
（2）返回值必须是unsigned long
（3）参数必须是一个32位值，如一个指针值或long类型
 (4) 如果函数是类成员函数，必须声明为static函数，在CreateThread时函数指针有特
 殊的写法。如下(函数是类CThreadTest的成员函数中)：
 static unsigned long _stdcall MyThreadFun(void* pParam);
 handleRet = CreateThread(NULL, 0, &CThreadTestDlg::MyThreadFun, NULL, 0, &ThreadID);
 之所以要声明为static是由于，该函数必须要独立于对象实例来使用，即使没有声明实例也可以
 使用。
*/

int QuickSort(long* Array, int iLow, int iHigh);     //快速排序


int main(int argc, char* argv[])
{
	/*
	//下面的代码是为了从命令行上接收参数进行排序的
	//但为了测试方便,所以就省去,改用静态数据进行排序
	//排序数据在接着的data数组里静态声明
	if(argc <= 1)
	{
		printf("Please Input Data.");
		return 0;
	}


	int i;
	long *data;
	int iDataLen = argc - 1;

	data = new long[argc-1];

	for (i=0; i<argc-1; i++)
	{
		data[i] = atol(argv[i+1]);
	}
	*/

	long data[] = {123,34,546,754,34,74,3,56};
	int iDataLen = 8;

	//为了对各个子线程分别对原始数据进行排序和保存排序结果
	//分别分配内存对data数组的数据进行复制
	long *data1, *data2, *data3, *data4, *data5;
	MySafeArray StructData1, StructData2, StructData3, StructData4;

	data1 = new long[iDataLen];
	memcpy(data1, data, iDataLen << 2); //把data中的数据复制到data1中
	//内存复制 memcpy(目标内存指针, 源内存指针, 复制字节数), 因为long的长度
	//为4字节,所以复制的字节数为iDataLen << 2, 即等于iDataLen*4
	StructData1.data = data1;
	StructData1.iLength = iDataLen;

	data2 = new long[iDataLen];
	memcpy(data2, data, iDataLen << 2);
	StructData2.data = data2;
	StructData2.iLength = iDataLen;

	data3 = new long[iDataLen];
	memcpy(data3, data, iDataLen << 2);
	StructData3.data = data3;
	StructData3.iLength = iDataLen;

	data4 = new long[iDataLen];
	memcpy(data4, data, iDataLen << 2);
	StructData4.data = data4;
	StructData4.iLength = iDataLen;

	data5 = new long[iDataLen];
	memcpy(data5, data, iDataLen << 2);


	unsigned long TID1, TID2, TID3, TID4; 

	//对信号量进行初始化
	evtTerminate = CreateEvent(NULL, FALSE, FALSE, "Terminate");
	evtPrint = CreateEvent(NULL, FALSE, TRUE, "PrintResult");
	//mtxPrint = CreateMutex(NULL, FALSE, "PrintMutex");
	//InitializeCriticalSection(&csPrint);

	//分别建立各个子线程
	CreateThread(NULL, 0, &BubbleSort, &StructData1, NULL, &TID1);
	CreateThread(NULL, 0, &SelectSort, &StructData2, NULL, &TID2);
	CreateThread(NULL, 0, &HeapSort, &StructData3, NULL, &TID3);
	CreateThread(NULL, 0, &InsertSort, &StructData4, NULL, &TID4);

	//在主线程中执行行快速排序，其他排序在子线程中执行
	QuickSort(data5, 0, iDataLen - 1);
	
	PrintResult(data5, iDataLen, "Quick Sort");

	WaitForSingleObject(evtTerminate, INFINITE); //等待所有的子线程结束
	//所有的子线程结束后，主线程才可以结束

	//delete[] data;
	delete[] data1;
	delete[] data2;
	delete[] data3;
	delete[] data4;

	CloseHandle(evtPrint);

	return 0;
}

/*
冒泡排序思想(升序，降序同理，后面的算法一样都是升序):
从头到尾对数据进行两两比较进行交换,小的放前大的放后。
这样一次下来，最大的元素就会被交换的最后，然后下一次
循环就不用对最后一个元素进行比较交换了，所以呢每一次
比较交换的次数都比上一次循环的次数少一，这样N次之后
数据就变得升序排列了
*/
unsigned long __stdcall BubbleSort(void* theArray)
{