VC中利用多线程技术实现线程之间的通信(8)

/*堆排序思想：堆：数据元素从1到N排列成一棵二叉树，而且这棵树的每一个子树的根都是该树中的元素的最小或最大的元素这样如果一个无序数据集合是一个堆那么，根元素就是最小或最大的元素堆排序就是不断对剩下的数据建堆，把最小或最大的元素析透出来。下面的算法，就是从最后一个元素开始，依据一个节点比父节点数值大的原则对所有元素进行调整，这样调整一次就形成一个堆，第一个元素就是最小的元素。然后再对剩下的无序数据再进行建堆，注意这时后面的无序数据元素的序数都要改变，如第一次建堆后，第二个元素就会变成堆的第一个元素。*/
unsigned long __stdcall HeapSort(void* theArray)
{
　long* Array = ((MySafeArray*)theArray)->data;
　int iLength = ((MySafeArray*)theArray)->iLength;
　int i, j, p;
　long swap;
　for(i=0; i　{
　　for(j = iLength - 1; j>i; j--) //从最后倒数上去比较字节点和父节点
　　{
　　　p = (j - i - 1)/2 + i; //计算父节点数组下标
　　　//注意到树节点序数跟数组下标不是等同的，因为建堆的元素个数逐个递减
　　　if(Array[j] < Array[p]) //如果父节点数值大则交换父节点和字节点
　　　{
　　　　swap = Array[j];
　　　　Array[j] = Array[p];
　　　　Array[p] = swap;
　　　}
　　}
　}
　PrintResult(Array, iLength, "Heap Sort"); //向控制台打印排序结果
　InterlockedIncrement(&ThreadCompleted); //返回前使线程完成数标记加1
　if(ThreadCompleted == 4) SetEvent(evtTerminate); //检查是否其他线程都已执行完
　//若都执行完则设置程序结束信号量
　return 0;
}

/*插入排序思想：把源数据序列看成两半，前面一半是有序的，后面一半是无序的，把无序的数据从头到尾逐个逐个的插入到前面的有序数据中，使得有序的数据的个数不断增大，同时无序的数据个数就越来越少，最后所有元素都会变得有序。*/
unsigned long __stdcall InsertSort(void* theArray)
{
　long* Array = ((MySafeArray*)theArray)->data;
　int iLength = ((MySafeArray*)theArray)->iLength;
　int i=1, j=0;
　long temp;
　for(i=1; i　{
　　temp = Array[i]; //取出序列后面无序数据的第一个元素值
　　for(j=i; j>0; j--) //和前面的有序数据逐个进行比较找出合适的插入位置
　　{
　　　if(Array[j - 1] >temp) //如果该元素比插入值大则后移
　　　　Array[j] = Array[j - 1];
　　　else //如果该元素比插入值小，那么该位置的后一位就是插入元素的位置
　　　　break;
　　}
　　Array[j] = temp;
　}
　PrintResult(Array, iLength, "Insert Sort"); //向控制台打印排序结果
　InterlockedIncrement(&ThreadCompleted); //返回前使线程完成数标记加1
　if(ThreadCompleted == 4) SetEvent(evtTerminate); //检查是否其他线程都已执行完
　　//若都执行完则设置程序结束信号量
　return 0;
}