我刚刚通过使用C++ 11可变参数模板在编译时对其进行评估来实现快速排序算法.但是,当数据集太大时,我遇到性能问题.
#include <iostream>
using namespace std;
template<int... vs>
struct Seq
{};
template<int v1, int...vs>
struct Seq<v1, vs...>{
};
template<typename newT, typename srcT>
struct PushFront{
};
template<int vadded, int...vs>
struct PushFront<Seq<vadded>, Seq<vs...>>{
typedef Seq<vadded, vs...> ResultType;
};
template<typename T>
struct PopFront{
};
template<int v1, int...vs>
struct PopFront<Seq<v1, vs...>>{
typedef Seq<vs...> RemaindType;
typedef Seq<v1> ResultType;
};
template<typename T1, typename T2>
struct CatSeq{};
template<int...v, int...us>
struct CatSeq<Seq<v...>, Seq<us...>>{
typedef Seq< v..., us... > ResultType;
};
template<bool c, typename NewT, typename TrueClsT, typename …所以Quicksort的空间效率是O(log(n)).这是维护调用堆栈所需的空间.
现在,根据Quicksort上的维基百科页面,这可以作为就地算法,因为算法只是交换输入数据结构中的元素.
然而,根据这个页面,空间效率O(log n)使Quicksort不合格,因为它的空间效率大于O(1).根据该定义,任何空间效率大于O(1)的算法都不是就地的.所以我认为这意味着根据定义,所有递归算法都没有到位？
显然,这里有两种不同的就地定义.维基百科并不总是一个完全可靠的来源,所以我咨询了我的一位教授.
我的教授同意第二个定义.他说Quicksort不到位.即使数据保留在输入数组中,堆栈所需的额外空间也会使其失去资格.我的教授写了一本关于算法的畅销书,所以我非常尊重他的观点,但这个答案对我来说似乎不正确.
我认为就地的属性非常直观.数据保持不变.它不会从它的原始数据结构中移动.对我来说,这个定义更有用,因为它意味着您可以使用指针执行算法,而不是要求您复制数据.这似乎是算法的一个有价值的属性,并且名副其实"就地".
algorithm computer-science quicksort in-place space-efficiency
我正在研究下面所需的程序,以便更好地理解它.
Quicksort最糟糕的运行时间是什么？可能导致这种更糟糕的情况？我们如何修改quicksort程序来缓解这个问题？
我知道它有最坏的情况O(n^2),我知道它是在枢轴唯一的最小或最大元素时发生的.我的问题是如何修改程序以缓解此问题.
一个好的算法会很好.
在许多情况下,快速排序比合并排序要好得多.但是,何时合并排序可能比快速排序更好？
例如,当数据无法一次加载到内存时,合并排序比快速排序更有效.还有其他案件吗？
编辑:建议的重复问题列表的答案快速排序合并排序的所有优点.我在这里询问可能的情况和使用合并排序的应用程序比使用快速排序更有利.
我对List Sort方法如何处理排序有疑问.鉴于以下要素:
class Element : IComparable<Element>
{
public int Priority { get; set; }
public string Description { get; set; }
public int CompareTo(Element other)
{
return Priority.CompareTo(other.Priority);
}
}
如果我尝试这样排序:
List<Element> elements = new List<Element>()
{
new Element()
{
Priority = 1,
Description = "First"
},
new Element()
{
Priority = 1,
Description = "Second"
},
new Element()
{
Priority = 2,
Description = "Third"
}
};
elements.Sort();
然后第一个元素是先前的第二个元素"Second".或者,换句话说,这个断言失败了:
Assert.AreEqual("First", elements[0].Description);
当元素基本相同时,为什么.NET重新排序我的列表？如果比较返回非零值,我希望它只对列表重新排序.
我找到了一种在quicksort中更有效地处理重复元素的方法,并且想知道是否有人之前已经看过这个.
这种方法大大减少了检查重复元素所涉及的开销,这有助于在有和没有重复元素的情况下提高性能.通常,重复的元素以几种不同的方式处理,我将首先列举.
首先,有荷兰国旗方法对数组进行排序[ < pivot | == pivot | unsorted | > pivot].
其次,有一种方法是在排序过程中将相等的元素放在最左边,然后将它们移动到排序中心[ == pivot | < pivot | unsorted | > pivot],然后在排序后将==元素移动到中心.
第三,Bentley-McIlroy分区将==元素放在两边,以便排序[ == pivot | < pivot | unsorted | > pivot | == pivot],然后==元素移动到中间.
最后两种方法是为了减少开销.
现在,让我解释一下我的方法如何通过减少比较次数来改进快速排序.我一起使用两个quicksort函数而不是一个.
我将调用的第一个函数q1,它将数组排序为[ < pivot | unsorted | >= pivot].
我将调用的第二个函数q2,它将数组排序为[ <= pivot | unsorted | > pivot].
现在让我们一起看看它们的用法,以便改进重复元素的处理.
首先,我们调用 …
如何为Java实现并发快速排序或合并排序算法？
我们在16-(虚拟) - 核心Mac上遇到了问题,其中只有一个核心(!)使用默认的Java排序算法工作,并且很好地看到非常好的机器完全未被充分利用.所以我们写了自己的(我写的),我们确实获得了很好的加速(我编写了一个多线程的快速排序,由于它的分区性质,它很好地并行化,但我也可以编写一个mergesort)...但是我的实现只能扩展最多4个线程,它是专有代码,我宁愿使用来自信誉良好的源代码而不是使用我重新发明的轮子.
我在Web上找到的唯一一个例子是如何不用 Java编写多线程快速排序,它使用的是繁忙循环(这非常糟糕):
while (helpRequested) { }
http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html
因此,除了无缘无故地丢失一个线程之外,它确保通过在while循环中忙碌循环来杀死perf(这是令人难以置信的).
因此我的问题是:您是否知道Java中正确的多线程快速排序或mergesort实现将来自信誉良好的来源？
我强调的事实是,我知道复杂性保持为O(n log n),但我仍然非常喜欢看到所有这些核心开始工作而不是空闲.请注意,对于其他任务,在相同的16个虚拟核心Mac上,我通过并行化代码看到了高达x7的加速(我并不意味着并发专家).
所以即使很难复杂性保持O(n log n),我也非常欣赏x7或x8甚至x16加速.
不插入排序O(n ^ 2)>快速排序O(nlogn)...所以对于小n,关系是否相同？
我刚刚回答了一个关于在快速实施中选择分区的不同方法的问题,并提出了一个我真的不知道如何回答的问题.这有点数学,这可能是错误的网站,所以如果这需要移动请告诉我,我很乐意将其迁移到其他地方.
众所周知,随机均匀选择其枢轴的快速实施将最终在预期的O(n lg n)时间内运行(在维基百科上有一个很好的证明).然而,由于产生随机数的成本,许多快速分类实现不会随机选择枢轴,而是依赖于"三分之一"方法,其中确定性地选择三个元素并且选择中值作为枢.众所周知,在最坏的情况下退化为O(n 2)(例如,参见关于如何生成那些最坏情况输入的大文章).
现在,假设我们通过从序列中挑选三个随机元素并使用它们的中位数作为枢轴的选择来组合这两种方法.我知道这也保证了O(n lg n)平均情况运行时使用的证据与常规随机快速排序的证明略有不同.但是,我不知道在这个特定的快速排序实现中,n ng n项前面的常数因子是什么.对于常规随机快速排序维基百科列出随机快速排序的实际运行时间最多需要1.39 n lg n比较(使用lg作为二进制对数).
我的问题是:有没有人知道如何使用"三分之一"随机快速排序得出比较次数的常数因子？如果我们更普遍地说,使用随机的k中值方法是否存在关于快速排序的常数因子的表达式？我很好奇,因为我觉得看看这种方法是否有一些"甜蜜点"比其他随机快速分析实施更少的比较会很有吸引力.我的意思是,能够说随机化的快速排序与随机中位数为六的枢轴选择使得比较最少,这不是很酷吗？或者能够最终说你应该随机选择一个枢轴元素？
在快速排序中选择枢轴值的三种策略的中位数是多少？
我在网上看到它,但我无法弄明白究竟是什么？以及它如何比随机快速排序更好.