文档介绍：精品资料
精品资料
并行排序算法
先简单说一下给的A, B, C三种算法(见上面引用的那篇博客)，A算
法将耗时的平方和开平方计算放到比较函数中，导致时，
每次亮亮比较都要执行平方和开平方计算，其平均算法复杂度为
O(nlog2n) 。而 B 将平方和开平方计算提取出来，算法复杂度降低
到O(n),这也就是为什么B比A效率要高很多的缘故。C和B相比，将平方函数替换成了 x*x ,由于少了远程函数调用和 Pow函数本身的开销，效率有提高了不少。我在 C的基础上编写了 D算法，D 算法采用并行计算技术，在我的双核笔记本电脑上数据量比较大的情
况下，其排序效率较C要提高30施右。
下面重点介绍这个并行排序算法。算法思路其实很简单，就是将
要排序的数组按照处理器数量等分成若干段，然后用和处理器数量等
同的线程并行对各个小段进行排序，排序结束和，再在单一线程中对
这若干个已经排序的小段进行归并排序，最后输出完整的排序结果。
考试大考虑到和 .Net 兼容，没有用微软提供的并行库，而是用
多线程来实现。
下面是测试结果：
n A B C D
32768
精品资料
精品资料
65535
131072
262144
524288
1048576
2097152
从测试结果上看，当要排序的数组长度较短时，并行排序的效率
甚至还没有不进行并行排序高，这主要是多线程的开销造成的。当数
组长度增大到 25 万以上时，并行排序的优势开始体现出来，随着数
组长度的增长，排序时间最后基本稳定在但线程排序时间的 74% 左
右，其中并行排序的消耗大概在 50%左右，归并排序的消耗在 14%左
右。由此也可以推断，如果在 4CPU勺机器上，其排序时间最多可以
减少到单线程的 14 + 25 = 39% 。 8 CPU 为 14 + = % 。
目前这个算法在归并算法上可能还有提高的余地，如果哪位高手
能够进一步提高这个算法，不妨贴出来一起交流交流。
下面分别给出并行排序和归并排序的代码：
并行排序类 ParallelSort
Paralletsort 类是一个通用的泛型，调用起来非常简单，下面
精品资料
精品资料
给一个简单的 int 型数组的排序示例：
class IntComparer : IComparer < int >
{
IComparer Members #region IComparer Members
public int Compare( int x, int y)
{
return (y);
}
#endregion
}
public void SortInt( int [] array)
{
< int > parallelSort = new
< int > ();
(array, new IntComparer());
ParallelSort 的
只要实现一个T类型两两比较的接口，然后调用
精品资料
精品资料
Sort 方法就可以了，是不是很简单 ?
下面是 ParallelSort 类的代码
using System;
using ;
using ;
using ;
using ;
namespace Sort
{
/**/ ///
/// ParallelSort
///
///
public class ParallelSort < T >
{
精品资料
{
精品资料
enum Status
{
{
精品资料
{
精品资料
Idle = 0 ,
Running = 1 ,
Finish = 2 ,
}
class ParallelEntity
{