基于.NET的常用排序方法以及运行时间比较

}}}}基于.NET的常用排序算法以及运行时间比较对集合进行排序是一种演示任务并行的方法。我们在这里对一个整数集合进行排序，当然，排序会存在不同的方法，在这里我们将使用三种常见的排序方法，以便找到最快的一种排序方法(当然这里的例子都是以升序方式排序的)。我们要比较的排序方法分别为：冒泡排序、插入排序和支点排序。当然在本例中，潜在的依赖是整数集合，他由不同的方法对集合同时进行排序。这是一个问题，因为整数集合正在被排序到适合的位置。有不同的技术可以解决依赖关系。一种解决方案是复制共享数据，并且给每个任务提供一个私有复制，这种方法是这里选择的方法；每个任务(排序算法)得到原始整数集合的复制作为参数。冒泡排序(BubbleSort )冒泡排序是一个常用的排序算法，不过这并不意味着它是一种最快的排序算法。实际上他有可能是最慢的排序方法之一。与其他排序方法比较，你就会发现冒泡排序是多么的慢。所以说，流行并不等于质量！冒泡排序执行的是二进制比较。他通常从集合的起点开始，并且比较最前面的两个元素。如果第二个元素小于第一个元素，则交换元素的位置。接着对第二个和第三个元素执行相同的比较和交换操作， 等等，知道集合的结尾。排序接着从起点重复，直到该集合被充分排序。下面是示例代码：{<Code1>#C#.NETCode#}publicstaticvoidBubbleSort(List<int>sortedList){inttemp,count=sortedList.Count;for(inti=0;i<count;++i){for(intj=0;j+1<count;++j){If(sortedList[j]>sortedList[j+1]){temp=sortedList[j];sortedList[j]=sortedList[j+1];sortedList[j+1]=temp;}#VB.NETCode#PublicSharedSubBubbleSort(ByValsortedListAsInteger())DimtempAsInteger,countAsInteger=sortedList.CountForIAsInteger=0Tocount -1Step1ForjAsInteger=0Tocount -2Step1IfsortedList(j)>sortedList(j+1)Thentemp=sortedList(j)sortedList(j)=sortedList(j+1)sortedList(j+1)=tempEndIfNextjNextiEndSub插入排序(InsertionSort)插入排序会迭代集合多次。每次迭代都将所选项目放到排序顺序中的正确位置。例如，初始迭代扫描集合，并将第一个元素放到排序序列的正确位置。第二次迭代再次扫描列表并将第二个元素放到正确位置。迭代继续，知道列表中的每个元素都被正确的定位。插入排序可以使用两种列表：未排序列表(输入)和排序列表(输出)；不过，这个例子只使用一个列表，执行排序到位。通过使用插入、重新配置和删除操作，排序重新配置每个元素。下面是具体的示例代码：{<Code2>#C#.NETCode#}publicstaticvoidInsertionSort(List<int>sortedList,CancellationTokentoken){intcurrentLocation,currentValue,insertionLocation,count=sortedList.Count;sortedList.Insert(0,0);for(intlocation=1;location<count+1;++location){currentLocation=location;insertionLocation=location —1;currentValue=sortedList[currentLcation];while(sortedList[insertionLocation]>currentValue){sortedList[currentLocation]=sortedList[insertionLocation];--currentLocation;--insertionLocation;}sortedList[currentLocation]=currentValue;}sortedList.Remove(0);}#VB.NETCode#PublicSharedSubInsertionSort(ByValsortedListAsInteger(),_ByValtokenAsCancellationToken)DimcountAsInteger=sortedList.CountDimcurrentLocation,currentValue,insertionLocationAsIntegersortedList.Insert(0,0)ForlocationAsInteger=1TocountStep1currentLocation=locationinsertionLocation=location -1currentValue=sortedList(currentLocation)DoWhilesortedList(currrentLocation)=sortedList(insertionLocation)sortedList(currentLocation)=sortedList(insertionLocation)currentLocation=currentLocation -1insertionLocation=insertionLocation-1LoopsortedList(currentLocation)=currentValueNextlocationsortedList.Remove(0)EndSub支点排序(PivotSort)支点排序就很有趣！支点排序就是俗称的快速排序(QuickSort)。该算法首先选择一个支点值，将集合分为两个集合。第一个集合包含小于支点值得元素，第二个集合包含大于支点值的元素。然后使用新的支点值在两个子集合中执行支点排序。继续递归划分和排序集合，直到每个子集合包含一个元素。最后组装排序的子集合来新建排序列表。因为本示例以升序排序，所以总是将较小的值放在左子集合，较大的放在右子集合。下面是示例代码：{<Code3>#C#.NETCode#}publicstaticvoidPivotSort(List<int>integerList,intbegin,intlast,intpivot){if(begin<last){pivot=integerList[last];intlocation=begin,bound=last;while(location<bound){if(integerList[location]<pivot){

++location;}else{integerList[bound]=integerList[location];integerList[location]=integerList[bound-1];--bound;}}integerList[bound]=pivot;PivotSort(integerList,begin,bound -1,pivot);PivotSort(integerList,bound+1,last,pivot);}}#VB.NETCode#PublicSharedSubPivotSort(ByValintegerListAsInteger(),_ByValbeginAsInteger,ByVallastAsInteger,_ByValpivotAsInteger)Ifbegin<lastThenpivot=integerList(last)DimlocationAsInteger=begin,boundAsInteger=lastDoWhilelocation<boundIfintegerList(location)<pivotThenlocation=location+1ElseintegerList(bound)=integerList(location)integerList(location)=integerList(bound-1)bound=bound-1EndIfLoopintegerList(bound)=pivotPivotSort(integerList,begin,bound -1,pivot)PivotSort(integerList,bound -1,last,pivot)EndIfEndSubFramework使用Barrier类对排序算法运行时间比较Framework为了使赛马公平，所有的马匹需要在同一时间开始起跑。赛马使用了首发门；同理Microsoft.NET提供了Barrier类。Barrier类位于System.Threading名空间。他是在提供了Barrier类。Barrier类位于System.Threading名空间。他是在Microsoft.NETFramework4中引入的。你可以使用Barrier类新建逻辑门或应用程序的各个阶段。初始化Barrier时，可以设置元素的最大数量。直到达到最大数量，给Barrier添加元素会阻挡当前任务当当Barrier 达到容量时会 泄露”此时，等待任务执行。所以当Barrier满时（所有马匹都在门口），它便释当当Barrier 达到容量时会 泄露”此时，等待任务执行。所以当Barrier满时（所有马匹都在门口），它便释放所有任务（比赛开始）下图说明了一个容量等于 3的BarrierT1BarrierBarrier泄露Barrier也可以把Barrier想成一个桶。当桶满了的时候,它会翻倒在地。当然，此时桶里的所有的东西都会被洒岀来了F面是Barrier类的一些有用的实例方法:T1BarrierBarrier泄露Barrier也可以把Barrier想成一个桶。当桶满了的时候,它会翻倒在地。当然，此时桶里的所有的东西都会被洒岀来了F面是Barrier类的一些有用的实例方法:1、 1、 Barrier constrauctor(intparticipantCount)新建一个Barrier实例并设置Barrier实例容量,对应VB.NET定义为FunctionConstrauctor(ByValparticipantCountAsInteger)AsBarrier2、voidSignalAndWait() 发岀信号，任务已达到Barrier ，对应的VB.NET定义为SubSignalAndWait()3、longAddParticoants(intparticipantCount) 增加Barrier 的容量，对应的VB.NET定义为FunctionAddParticoants(ByValparticipantCountAsInteger)AsLong4、voidRemovePaticipants(intparticipantCount) 减少Barrier 的容量，对应的VB.NET定义为SubRemovePaticipants(ByValparticipantCountAsInteger)这个排序例子使用一个 Barrier 来标记排序阶段的开始。Barrier的最大值设置为3(冒泡、插入和支点排序)使用Barrier 可以保证三种排序程序同时开始，从而保证了比赛的公平性。每种算法在一个单独的代码域开始。每个区域都遵循下面这个相同的通用模式。1、复制列表运行这段代码，将得到一个类似下图的结果，显示对 运行这段代码，将得到一个类似下图的结果，显示对 10000 个整数排序的以毫秒计数的持续时间结果。最终获2、新建排序算法任务。3、任务：向Barrier发信号。4、任务：执行排序。5、启动任务。下面是插入排序区域，是三个排序区域的其中一个。下面代码需要导入System.Threading 和System.Threading.Tasks 命名空间，并且需要使用4.0以及更高版本的Microsoft.NETFramework 。下面是示例代码：{<Code4>#C#.NETCode#}//InsertionSortRegionList<int>insertionList=integerList.ToList();TasktaskInsertionSort=newTask(()=>{sortBarrier.SignalAndWait();using(newSortResults( “InsertionSort”)){SortAlgorithms.InsertionSort(insertionList);}});taskInsertionSort.Start();#VB.NETCode#,InsertionSortRegionDiminsertionListAsInteger()=integerList.ToList()DimtaskInsertionSortAsTask=NewTask(Function()sortBarrier.SignalAndWait()UsingNewSortResults(“InsertionSort”)){SortAlqorithms.InsertionSort(insertionList)}}EndFunction)taskInsertionSort.Start()还需要一些代码来显示每种排序算法的持续时间，以便找到哪种排序最快。这段代码等待排序任务完成，然后迭代并显示结果：{<Code5>#C#.NETCode#}Task.WaitAll(newTask[]{taskBubbleSort,taskInsertionSort,taskPivotSort});foreach(stringresultinSortResults.results){Console.WriteLine(result);}#VB.NETCode#Task.WaitAll(NewTask(){taskBubbleSort,taskInsertionSort,taskPivotSort})ForEachresultAsStringInSortResults.resultsConsole.WriteLine(result)Next胜者是----支点排序！这场比赛甚至还没有结束。file:///C:/Users/DickSmith/AppData/Local/Temp.„PivotSar*t：161msIn#佯MionSort=39,509nsBubbleSort=167,389ms代码在哪里计算持续时间呢？首先，一个在System.Diagnosties 命名空间定义的Stopwatch 类被用来跟踪每个算法的持续时间。在本示例程序中，SortResults 是类Stopwatch 类的一个封装，计算一个排序算法的持续时间以下是对SortResults类的一般描述：1、在SortResults类中，新建一个Stopwatch 类的实例作为成员域。2、 构造函数调用Stopwatch市里的Start方法，并设置算法的名称。3、Dispose 方法调用Stopwatch的Stop方法。结果接着被实例化并添加到结果集合。该结果集合随后