学习LINQ：QuickSort
今天下午，我参加了这次尝试，并开始学习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来处理它不适用的东西？
只需将参数的类型更改为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));
}
希望这可以帮助。
有趣的问题！ 这不会超越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，因为我的QSorted时，键== 0。
为了好玩，我测试了这些解决方案。 我提交了主要的性能测试罪（在调试模式下进行测试），但我认为这并不影响我们将看到的大O效应。 这里是输入（反向输入是快速排序的最坏情况）
IEnumerable<int> source = Enumerable.Range(0, 1000).Reverse().ToList();
这个怎么样？ （如果我理解的很好，你不喜欢.ToList调用）
public static IEnumerable<int> QSLinq(IEnumerable<int> items)
{
if (items.Count() <= 1)
return items;
int pivot = items.First();
return QSLinq(items.Where(i => i < pivot))
.Concat(items.Where(i => i == pivot))
.Concat(QSLinq(items.Where(i => i > pivot)));
}
基于Jon的免责声明回答： 不要在实际问题中使用此算法。 这是非常低效的。
链接地址: http://www.djcxy.com/p/51325.html