c# - 排序子序列的最有效排序算法

Question

我有几个 long 类型（升序）数字的排序序列，并希望生成一个包含相同顺序的所有元素的主序列。我寻找最有效的排序算法来解决这个问题。我以 C#、.Net 4.0 为目标，因此也欢迎针对并行性的想法。

这是一个示例：
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

编辑：当有两个（或更多）相同的值时，这两个（或更多）的顺序无关紧要。

Answer 1

只需合并序列。您不必再次对它们进行排序。

Answer 2

我知道没有 .NET Framework 方法可以进行 K 路合并。通常，它是通过优先级队列（通常是堆）完成的。做起来不难，效率也很高。给定 K 个排序列表，共包含 N 个项目，复杂度为 O(N log K)。

我在我的文章A Generic Binary Heap Class中展示了一个简单的二进制堆类。在对大文本文件进行排序中，我介绍了创建多个排序的子文件并使用堆进行 K 路合并。给定一个小时（也许更少）的学习时间，您可能可以调整它以在您的程序中使用。

Answer 3

您只需要像合并排序一样合并您的序列。

这是可并行的：

1. 合并序列（1/2 中的 1 和 2），（3/4 中的 3 和 4），...</li>
2. 合并序列（1/2/3/4 中的 1/2 和 3/4），（5/6/7/8 中的 5/6 和 7/8），...</li>
3. …</li>

这是合并功能：

int j = 0;
int k = 0;
for(int i = 0; i < size_merged_seq; i++)
{
  if (j < size_seq1 && seq1[j] < seq2[k])
  {
    merged_seq[i] = seq1[j];
    j++;
  }
  else
  {
    merged_seq[i] = seq2[k];
    k++;
  }
}

Answer 4

简单的方法是将它们一一合并。但是，这将需要O(n*k^2)时间，其中k是序列数，是序列n中的平均项目数。但是，使用分而治之的方法，您可以将此时间降低到 O(n*k*log k)。算法如下：

1. 将 k 序列划分为 k/2 组，每组 2 个元素（如果 k 为奇数，则为 1 组，每组 1 个元素）。
2. 合并每组中的序列。因此，您将获得 k/2 个新组。
3. 重复直到你得到一个序列。

Answer 5

更新：

事实证明，使用所有算法......简单的方法仍然更快：

private static List<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedBunches)
{
    var list = sortedBunches.SelectMany(bunch => bunch).ToList();

    list.Sort();

    return list;
}

并且出于遗留目的...

这是按优先级排序的最终版本：

    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());
    }