对排序的子序列最有效的排序算法 [英] Most efficient sorting algorithm for sorted sub-sequences
问题描述
我型长(升序)的数数排序的序列,并希望生成包含在同一个订单中所有的元素一个主序列。我寻找最有效的排序算法来解决这个问题。我针对C#.NET 4.0中,因此也欢迎针对并行的想法。
I have several sorted sequences of numbers of type long (ascending order) and want to generate one master sequence that contains all elements in the same order. I look for the most efficient sorting algorithm to solve this problem. I target C#, .Net 4.0 and thus also welcome ideas targeting parallelism.
下面是一个例子:
S1 = 1,2,3,5,7,13
S2 = 2,3,6
S3 = 4,5,6,7,8
所得序列= 1,2,2,3,3,4,5,5,6,6,7,7,8,13
Here is an example:
s1 = 1,2,3,5,7,13
s2 = 2,3,6
s3 = 4,5,6,7,8
resulting Sequence = 1,2,2,3,3,4,5,5,6,6,7,7,8,13
编辑:当有两个(或更多)相同的值则顺序这两个(或更多个)也没有关系
When there are two (or more) identical values then the order of those two (or more) does not matter.
推荐答案
更新:
原来,所有的算法,...这是仍然较快的简单方法:
Turns out that with all the algorithms... It's still faster the simple way:
private static List<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedBunches)
{
var list = sortedBunches.SelectMany(bunch => bunch).ToList();
list.Sort();
return list;
}
和遗留的目的...
下面是最后的版本,优先考虑:
Here is the final version by prioritizing:
private static IEnumerable<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedInts) where T : IComparable<T>
{
var enumerators = new List<IEnumerator<T>>(sortedInts.Select(ints => ints.GetEnumerator()).Where(e => e.MoveNext()));
enumerators.Sort((e1, e2) => e1.Current.CompareTo(e2.Current));
while (enumerators.Count > 1)
{
yield return enumerators[0].Current;
if (enumerators[0].MoveNext())
{
if (enumerators[0].Current.CompareTo(enumerators[1].Current) == 1)
{
var tmp = enumerators[0];
enumerators[0] = enumerators[1];
enumerators[1] = tmp;
}
}
else
{
enumerators.RemoveAt(0);
}
}
do
{
yield return enumerators[0].Current;
} while (enumerators[0].MoveNext());
}
这篇关于对排序的子序列最有效的排序算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!