并行排序算法Word文件下载.doc

并行排序算法Word文件下载.doc

《并行排序算法Word文件下载.doc》由会员分享，可在线阅读，更多相关《并行排序算法Word文件下载.doc（24页珍藏版）》请在冰点文库上搜索。

　　下面分别给出并行排序和归并排序的代码：

　　并行排序类ParallelSort

　　Paralletsort类是一个通用的泛型，调用起来非常简单，下面给一个简单的int型数组的排序示例：

　　classIntComparer:

IComparer<

int>

　　{

　　IComparerMembers#regionIComparerMembers

　　publicintCompare（intx,inty）

　　returnx.CompareTo（y）;

　　}

　　#endregion

　　publicvoidSortInt（int[]array）

　　Sort.ParallelSort<

parallelSort=newSort.ParallelSort<

（）;

　　parallelSort.Sort（array,newIntComparer（））;

只要实现一个T类型两两比较的接口，然后调用ParallelSort的Sort方法就可以了，是不是很简单?

　　下面是ParallelSort类的代码

　　usingSystem;

　　usingSystem.Collections.Generic;

　　usingSystem.Linq;

　　usingSystem.Text;

　　usingSystem.Threading;

　　namespaceSort

　　/**////

　　///ParallelSort

　　///

　　publicclassParallelSort<

T>

　　enumStatus

　　Idle=0,

　　Running=1,

　　Finish=2,

　　classParallelEntity

　　publicStatusStatus;

　　publicT[]Array;

　　publicIComparer<

Comparer;

　　publicParallelEntity（Statusstatus,T[]array,IComparer<

comparer）

　　Status=status;

　　Array=array;

　　Comparer=comparer;

　　privatevoidThreadProc（ObjectstateInfo）

　　ParallelEntitype=stateInfoasParallelEntity;

　　lock（pe）

　　pe.Status=ParallelSort<

.Status.Running;

　　Array.Sort（pe.Array,pe.Comparer）;

.Status.Finish;

　　publicvoidSort（T[]array,IComparer<

　　//Calculateprocesscount

　　intprocessorCount=Environment.ProcessorCount;

　　//Ifarray.Lengthtooshort,donotuseParallelsort

　　if（processorCount==1||array.Length<

processorCount）

　　Array.Sort（array,comparer）;

　　return;

　　//Splitarray

　　ParallelEntity[]partArray=newParallelEntity[processorCount];

　　intremain=array.Length;

　　intpartLen=array.Length/processorCount;

//Copydatatosplitedarray

　　for（inti=0;

i<

processorCount;

i++）

　　if（i==processorCount-1）

　　partArray[i]=newParallelEntity（Status.Idle,newT[remain],comparer）;

　　else

　　partArray[i]=newParallelEntity（Status.Idle,newT[partLen],comparer）;

　　remain-=partLen;

　　Array.Copy（array,i*partLen,partArray[i].Array,0,partArray[i].Array.Length）;

　　//Parallelsort

processorCount-1;

　　ThreadPool.QueueUserWorkItem（newWaitCallback（ThreadProc）,partArray[i]）;

　　ThreadProc（partArray[processorCount-1]）;

　　//Waitallthreadsfinish

　　while（true）

　　lock（partArray[i]）

　　if（partArray[i].Status==ParallelSort<

.Status.Finish）

　　break;

　　Thread.Sleep（0）;

//Mergesort

　　MergeSort<

mergeSort=newMergeSort<

　　List<

T[]>

source=newList<

（processorCount）;

　　foreach（ParallelEntitypeinpartArray）

　　source.Add（pe.Array）;

　　mergeSort.Sort（array,source,comparer）;

　　多路归并排序类MergeSort

　　///MergeSort

　　publicclassMergeSort<

　　publicvoidSort（T[]destArray,List<

source,IComparer<

　　//MergeSort

　　int[]mergePoint=newint[source.Count];

source.Count;

　　mergePoint[i]=0;

　　intindex=0;

　　while（index<

destArray.Length）

　　intmin=-1;

　　if（mergePoint[i]>

=source[i].Length）

　　continue;

　　if（min<

0）

　　min=i;

　　if（comparer.Compare（source[i][mergePoint[i]],source[min][mergePoint[min]]）<

　　destArray[index++]=source[min][mergePoint[min]];

　　mergePoint[min]++;

　主函数及测试代码在蛙蛙池塘代码基础上修改

　　usingSystem.Diagnostics;

　　namespaceVector4Test

　　publicclassVector

　　publicdoubleW;

　　publicdoubleX;

　　publicdoubleY;

　　publicdoubleZ;

　　publicdoubleT;

　　internalclassVectorComparer:

Vector>

　　publicintCompare（Vectorc1,Vectorc2）

　　if（c1==null||c2==null）

　　thrownewArgumentNullException（"

Bothobjectsmustnotbenull"

）;

　　doublex=Math.Sqrt（Math.Pow（c1.X,2）

　　+Math.Pow（c1.Y,2）

　　+Math.Pow（c1.Z,2）

　　+Math.Pow（c1.W,2））;

　　doubley=Math.Sqrt（Math.Pow（c2.X,2）

　　+Math.Pow（c2.Y,2）

　　+Math.Pow（c2.Z,2）

　　+Math.Pow（c2.W,2））;

　　if（x>

y）

　　return1;

　　elseif（x<

　　return-1;

　　return0;

　　internalclassVectorComparer2:

　　if（c1.T>

c2.T）

　　elseif（c1.T<

　　internalclassProgram

　　privatestaticvoidPrint（Vector[]vectors）

　　//foreach（Vectorvinvectors）

　　//{

　　//Console.WriteLine（v.T）;

　　//}

privatestaticvoidMain（string[]args）

　　Vector[]vectors=GetVectors（）;

　　Console.WriteLine（string.Format（"

n={0}"

vectors.Length））;

　　Stopwatchwatch1=newStopwatch（）;

　　watch1.Start（）;

　　A（vectors）;

　　watch1.Stop（）;

　　Console.WriteLine（"

Asorttime:

"

+watch1.Elapsed）;

　　Print（vectors）;

　　vectors=GetVectors（）;

　　watch1.Reset（）;

　　B（vectors）;

Bsorttime:

　　C（vectors）;

Csorttime:

　　D（vectors）;

Dsorttime:

　　Console.ReadKey（）;

　　privatestaticVector[]GetVectors（）

　　intn=1<

<

21;

　　Vector[]vectors=newVector[n];

　　Randomrandom=newRandom（）;

n;

　　vectors[i]=newVector（）;

　　vectors[i].X=random.NextDouble（）;

　　vectors[i].Y=random.NextDouble（）;

　　vectors[i].Z=random.NextDouble（）;

　　vectors[i].W=random.NextDouble（）;

　　returnvectors;

　　privatestaticvoidA（Vector[]vectors）

　　Array.Sort（vectors,newVectorComparer（））;

　　privatestaticvoidB（Vector[]vectors）

　　intn=vectors.Length;

　　Vectorc1=vectors[i];

　　c1.T=Math.Sqrt（Math.Pow（c1.X,2）

Array.Sort（vectors,newVectorComparer2（））;

　　privatestaticvoidC（Vector[]vectors）

　　c1.T=Math.Sqrt（c1.X*c1.X

　　+c1.Y*c1.Y

　　+c1.Z*c1.Z

　　+c1.W*c1.W）;

　　Array.Sort（vectors,newVectorComparer2（））;

　　privatestaticvoidD（Vector[]vectors）

　　parallelSort.Sort（vectors,newVectorComparer2（））;