如何重构这个例程来避免使用递归的？

Question

因此，我正在写一归并中的 C＃作为锻炼，虽然它的工作，在代码回头看，还有改进的余地。

基本上，该算法的第二部分需要一个例程为合并两个已排序的列表即可。

下面是我的路太长的实现，可以使用一些重构：

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    if (sLeft.Count == 0 || sRight.Count == 0)
    {
        sLeft.AddRange(sRight);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count == 1)
    {
        if (sLeft[0] <= sRight[0])
            sLeft.Add(sRight[0]);
        else
            sLeft.Insert(0, sRight[0]);
        return sLeft;
    }
    else if (sLeft.Count == 1 && sRight.Count > 1)
    {
        for (int i=0; i<sRight.Count; i++)
        {
            if (sLeft[0] <= sRight[i])
            {
                sRight.Insert(i, sLeft[0]);
                return sRight;
            }
        }
        sRight.Add(sLeft[0]);
        return sRight;
    }
    else if (sLeft.Count > 1 && sRight.Count == 1)
    {
        for (int i=0; i<sLeft.Count; i++)
        {
            if (sRight[0] <= sLeft[i])
            {
                sLeft.Insert(i, sRight[0]);
                return sLeft;
            }
        }
        sLeft.Add(sRight[0]);
        return sLeft;
    }
    else
    {
        List<int> list = new List<int>();
        if (sLeft[0] <= sRight[0])
        {
            list.Add(sLeft[0]);
            sLeft.RemoveAt(0);
        }
        else
        {
            list.Add(sRight[0]);
            sRight.RemoveAt(0);
        }

        list.AddRange(MergeSortedLists(sLeft, sRight));
        return list;
    }       
}

当然这个例程可以改善/通过去除缩短递归等甚至有其他的方法来合并2排序的列表。因此，任何重构是值得欢迎的。

虽然我确实有一个答案，我很好奇，如何将其他程序员会去改善这个程序。

谢谢！

Answer 1

作为一个起点，我会删除你的特殊情况为当列表或者具有Count == 1 - 他们可以通过你的更普遍（目前递归）的情况下进行处理。

在if (sLeft.Count > 1 && sRight.Count == 0)会的从不的，因为你已经检查sRight.Count == 0在一开始是真实的 - 所以这个代码将永远不会到达，是多余的。

最后，而不是递归（这是在这种情况下，非常昂贵，由于新的列表创建的数量 - 每一个元素），我会做这样的事情在你的else（实际上，这可能替换整个法）：

List<int> list = new List<int>();

while (sLeft.Count > 0 && sRight.Count > 0)
{
    if (sLeft[0] <= sRight[0])
    {
        list.Add(sLeft[0]);
        sLeft.RemoveAt(0);
    }
    else
    {
        list.Add(sRight[0]);
        sRight.RemoveAt(0);
    }
}

// one of these two is already empty; the other is in sorted order...
list.AddRange(sLeft);
list.AddRange(sRight);
return list;

（理想情况下我会重构这个以整数索引使用针对每个列表，而是采用.RemoveAt，因为它是通过列表不是破坏它更高性能的循环，因为它可能会离开原来的清单完整有用的。这仍是更有效的代码比原来的，虽然！）

Answer 2

合并两个排序的列表可以在O（n）的进行。

List<int> lList, rList, resultList;
int r,l = 0;

while(l < lList.Count && r < rList.Count)
{
  if(lList[l] < rList[r]
    resultList.Add(lList[l++]);
  else
    resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
  resultList.Add(lList[l++]);
while(r < rList.Count)
  resultList.Add(rList[r++]);

Answer 3

我在此采取将是：

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    List<int> result = new List<int>();
    int indexLeft = 0;
    int indexRight = 0;

    while (indexLeft < sLeft.Count || indexRight < sRight.Count)
    {
        if (indexRight == sRight.Count ||
            (indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
        {
            result.Add(sLeft[indexLeft]);
            indexLeft++;
        }
        else
        {
            result.Add(sRight[indexRight]);
            indexRight++;
        }
    }
    return result;
}

如果我不得不做手工我会做什么。 =）

Answer 4

您真的确定你的代码工作呢？没有测试它，我看到以下：

...
else if (sLeft.Count > 1 && sRight.Count == 0)  //<-- sRight is empty
{
    for (int i=0; i<sLeft.Count; i++)
    {
        if (sRight[0] <= sLeft[i]) //<-- IndexError?
        {
            sLeft.Insert(i, sRight[0]);
            return sLeft;
        }
    }
    sLeft.Add(sRight[0]);
    return sLeft;
}
...

Answer 5

您被要求differrent方法为好。我可能会做如根据使用情况如下。下面的代码是懒所以不会在排序整个列表一次，但只有当被要求的元件。

class MergeEnumerable<T> : IEnumerable<T>
    {
        public IEnumerator<T> GetEnumerator()
        {
            var left = _left.GetEnumerator();
            var right = _right.GetEnumerator();
            var leftHasSome = left.MoveNext();
            var rightHasSome = right.MoveNext();
            while (leftHasSome || rightHasSome)
            {
                if (leftHasSome && rightHasSome)
                {
                  if(_comparer.Compare(left.Current,right.Current) < 0)
                  {
                    yield return returner(left);
                  } else {
                    yield return returner(right);
                  }
                }
                else if (rightHasSome)
                {
                    returner(right);
                }
                else
                {
                    returner(left);
                }
            }
        }

        private T returner(IEnumerator<T> enumerator)
        {
            var current = enumerator.Current;
            enumerator.MoveNext();
            return current;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        private IEnumerable<T> _left;
        private IEnumerable<T> _right;
        private IComparer<T> _comparer;

        MergeEnumerable(IEnumerable<T> left, IEnumerable<T> right, IComparer<T> comparer)
        {
            _left = left;
            _right = right;
            _comparer = comparer;
        }
    }

编辑：这是基本相同implementatin作为谢尔盖Osypchuk他的意志从开始到结束只在看的时候排序是最快的，但延迟会更高，以及由于分拣整个的事实清单前期。因此，正如我所说的根据使用情况我可能会使用这种方法去替代将类似于谢尔盖Osypchuk

的东西

Answer 6

通常可以使用一个堆栈，而不是使用递归

Answer 7

合并列表（由理论，输入列表被预先排序）分选可在下列方式来实现：

List<int> MergeSorting(List<int> a, List<int> b)
    {
        int apos = 0;
        int bpos = 0;
        List<int> result = new List<int>();
        while (apos < a.Count && bpos < b.Count)
        {
            int avalue = int.MaxValue;
            int bvalue = int.MaxValue;
            if (apos < a.Count)
                avalue = a[apos];
            if (bpos < b.Count)
                bvalue = b[bpos];
            if (avalue < bvalue)
            {
                result.Add(avalue);
                apos++;
            }
            else
            {
                result.Add(bvalue);
                bpos++;
            }
        }
        return result;
    }

在的情况下开始与未排序的列表需要通过分选的亚序列分割它比玛吉他们使用上文

功能

Answer 8

我从来没有使用递归归并排序。你可以反复经过的投入，采取的事实，即排序的块大小双打每一个合并通。跟踪块大小和你从每个输入表处理的项目数的;当他们相等，则列表被耗尽。当两个列表是筋疲力尽，你可以移动到下一对块。当块大小是大于或等于您输入的大小，你就大功告成了。

编辑：一些我以前留下的信息是不正确的，因为我的误解 - 在C＃列表类似于一个数组，而不是一个链表。我的道歉。