学习LINQ:QuickSort

Question

我今天下午开始学习LINQ,到目前为止只是在LINQ上收集品牌.我尝试的第一件事就是实现QSort.

现在 - 忽略我可以使用ORDERBY并且这是一个非常愚蠢的qsort实现的事实- 我想出的是:

public class lqsort
{
    public static List<int> QSLinq(List<int> _items)
    {
        if (_items.Count <= 1)
            return _items;

        int _pivot = _items[0];

        List<int> _less = (from _item in _items where _item < _pivot select _item).ToList();
        List<int> _same = (from _item in _items where _item == _pivot select _item).ToList();
        List<int> _greater = (from _item in _items where _item > _pivot select _item).ToList();

        return (QSLinq(_less).Concat(_same.Concat(QSLinq(_greater)))).ToList();
    }
}

唯一真正让我烦恼的是所涉及的所有演员.我可能会使用任何LINQ技巧吗？或者我只是将LINQ用于不适合的事情？

Answer 1

只需将参数类型更改为IEnumerable并使用var构造而不是List<int>您的局部变量.

这将使您的QSLinq方法更好,因为它将接受更多类型的参数,例如int[],以及List<int>.

看到新方法:

    public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
    {
        if (_items.Count() <= 1)
            return _items;

        var _pivot = _items.First();

        var _less = from _item in _items where _item < _pivot select _item;
        var _same = from _item in _items where _item == _pivot select _item;
        var _greater = from _item in _items where _item > _pivot select _item;

        return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
    }

希望这可以帮助.

Answer 2

有趣的问题!这并不比OrderBy好,但它确实限制了重复的枚举.

    public static IEnumerable<int> QSort2(IEnumerable<int> source)
    {
        if (!source.Any())
            return source;
        int first = source.First();
        return source
            .GroupBy(i => i.CompareTo(first))
            .OrderBy(g => g.Key)
            .SelectMany(g => g.Key == 0 ? g : QSort2(g));
    }

我在开发过程中无意中生成了一个stackoverflow,因为我在Key == 0时QSorted.

为了好玩,我测试了这些解决方案.我提交了基本性能测试罪(在调试模式下测试),但我认为这不会影响我们将看到的大O效应.这是输入(反向输入是quicksort的最坏情况)

IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();

• 三连续解决方案耗时71000毫秒.
• 我的解决方案需要330毫秒
• OrderBy.ToArray花了15毫秒(计时器的分辨率,因此实际时间可能更短)