临界区的互斥控制

　2009-11-01 20:31:15　来源：WEB开发网　　　

核心提示：堆：数据元素从1到N排列成一棵二叉树，而且这棵树的每一个子树的根都是该树中的元素的最小或最大的元素这样如果一个无序数据集合是一个堆那么，临界区的互斥控制(4)，根元素就是最小或最大的元素 ,堆排序就是不断对剩下的数据建堆，把最小或最大的元素析透出来，最后使用递归对左右两部分进行同样处理.int QuickSort(lo

堆：数据元素从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; ii; 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; }

3.4 插入排序思想：

把源数据序列看成两半，前面一半是有序的，后面一半是无序的，把无序的数据从头到尾逐个逐个的插入到前面的有序数据中，使得有序的数据的个数不断增大，同时无序的数据个数就越来越少，最后所有元素都会变得有序。

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; i0; 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; }

3.5 快速排序思想：

快速排序是分治思想的一种应用，它先选取一个支点，然后把小于支点的元素交换到支点的前边，把大于支点的元素交换到支点的右边。然后再对支点左边部分和右边部分进行同样的处理，这样若干次之后，数据就会变得有序。

下面的实现使用了递归

建立两个游标：iLow，iHigh；iLow指向序列的第一个元素，iHigh指向最后一个先选第一个元素作为支点，并把它的值存贮在一个辅助变量里。那么第一个位置就变为空并可以放置其他的元素。这样从iHigh指向的元素开始向前移动游标iHigh查找比支点小的元素，如果找到，则把它放置到空置了的位置（现在是第一个位置）然后iHigh游标停止移动，这时iHigh指向的位置被空置，然后移动iLow游标寻找比支点大的元素放置到iHigh指向的空置的位置，如此往复直到iLow与iHigh相等。最后使用递归对左右两部分进行同样处理.

int QuickSort(long* Array, int iLow, int iHigh) { 　　if(iLow >= iHigh) return 1; //递归结束条件　　long pivot = Array[iLow]; 　　int iLowSaved = iLow, iHighSaved = iHigh; //保未改变的iLow，iHigh值保存起来　　while (iLow < iHigh) 　　{ 　　　　while (Array[iHigh] >= pivot && iHigh > iLow) //寻找比支点大的元素　　　　iHigh -- ; 　　　　Array[iLow] = Array[iHigh]; //把找到的元素放置到空置的位置　　　　while (Array[iLow] < pivot && iLow < iHigh) //寻找比支点小的元素　　　　　iLow ++ ; 　　　　Array[iHigh] = Array[iLow]; //把找到的元素放置到空置的位置　　} 　　Array[iLow] = pivot; //把支点值放置到支点位置，这时支点位置是空置的　　//对左右部分分别进行递归处理　　QuickSort(Array, iLowSaved, iHigh-1); 　　QuickSort(Array, iLow+1, iHighSaved); 　　return 0; }