并行排序算法 [英] Parallel Sort Algorithm

问题描述

我在找一个简单的实现并行（多线程）排序算法在C＃中，可以在名单，其中经营的; T＆GT; 或阵列，并有可能使用并行扩展但该部分不是严格必需的。

I'm looking for a simple implementation of a parallelized (multi-threaded) sort algorithm in C# that can operate on List<T> or Arrays, and possibly using Parallel Extensions but that part isn't strictly necessary.

编辑：弗兰克·克鲁格提供了一个很好的答案，但是我想这个例子转换为一个不使用LINQ。还要注意的是 Parallel.Do（）似乎已经被取代由 Parallel.Invoke（）。

Frank Krueger provides a good answer, however I wish to convert that example to one that doesn't use LINQ. Also note that Parallel.Do() seems to have been superceded by Parallel.Invoke().

感谢。

推荐答案

摘自阴暗面，在他的文章<一个href="http://www.darkside.co.za/archive/2008/03/14/microsoft-parallel-extensions-.net-framework.aspx">Parallel扩展.NET框架我们有这个并行扩展版本的快速排序的：

From "The Darkside" in his article Parallel Extensions to the .Net Framework we have this parallel extensions version of quicksort:

private void QuicksortSequential<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    if (right > left)
    {
        int pivot = Partition(arr, left, right);
        QuicksortSequential(arr, left, pivot - 1);
        QuicksortSequential(arr, pivot + 1, right);
    }
}

private void QuicksortParallelOptimised<T>(T[] arr, int left, int right) 
where T : IComparable<T>
{
    const int SEQUENTIAL_THRESHOLD = 2048;
    if (right > left)
    {
        if (right - left < SEQUENTIAL_THRESHOLD)
        {

            QuicksortSequential(arr, left, right);
        }
        else
        {
            int pivot = Partition(arr, left, right);
            Parallel.Do(
                () => QuicksortParallelOptimised(arr, left, pivot - 1),
                () => QuicksortParallelOptimised(arr, pivot + 1, right));
        }
    }
}

注意，他恢复到一个顺序排序一旦项目数小于2048

Notice that he reverts to a sequential sort once the number of items is less than 2048.

这篇关于并行排序算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！