排序子序列的最有效排序算法

本文关键字：排序 有效 算法 | 更新日期: 2023-09-27 18:33:16

我有几个长（升序）类型的数字排序序列，并希望生成一个包含相同顺序的所有元素的主序列。我寻找最有效的排序算法来解决这个问题。我的目标是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

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

排序子序列的最有效排序算法

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

据我所知，没有.NET Framework方法可以进行K-way合并。通常，它是通过优先级队列（通常是堆）完成的。这并不难做到，而且效率很高。给定 K 个排序列表，一起包含 N 个项目，复杂度为 O（N log K）。

我在文章通用二进制堆类中展示了一个简单的二进制堆类。在对大型文本文件进行排序中，我将演练如何创建多个排序的子文件，并使用堆进行 K-way 合并。给定一个小时（也许更少）的学习时间，您可能会将其调整以用于您的程序。

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

这是可并行化的：

    合并序列（1/2
  1. 中的 1 和 2）、（3/4 中的 3 和 4）、...
    2. 合并序列（1/2/3/4 中的
  2. 1/2 和 3/4）、（5/6 和 7/8 中的 5/6/7/8）、...
  3. 。

这是合并函数：

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++;
  }
}

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

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

更新：

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

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());
    }
相关文章：