什么是随机浮点数的最佳排序算法？

我的一位同事刚把这个问题在今天下午提出来，让我有点好奇。我对排序算法很熟悉，但缺乏正式学位（我不愿意承认），但我不能真正将我的指点放在这一点上。：p什么是随机浮点数的最佳排序算法？

噢，是的，这在C＃/ .NET实现的环境中是很温和的......以防万一有所改变。

谢谢你们。 :)

2010-07-13 Richard Neil Ilagan

有多少浮子？ 3？ 300？ 3百万？ – 2010-07-13 12:00:23

是什么让浮点数与int不同？除了渐近复杂性，您是否正在考虑性能度量？ – Mau 2010-07-13 12:04:22

要回答格雷格，我真的不知道。：D这是一个普遍的问题，这让我想要寻找一般的答案，而这个答案在大多数时候最可能是最优的。：p用户mdma提供了一个很好的参数，可以在快速排序和合并排序之间进行选择，而无需在一定数量的元素上进行锚定。 :) – 2010-07-13 12:21:02

对于固定长度的数字，你不局限于基于比较的排序算法，所以O(n*log(n))是不极限。 Radix Sort在O(n)中工作，由于IEEE 754浮点数在将其位模式解释为整数时正确排序的惊人特性，可以非常方便地使用。

来源

2010-07-13 12:22:12

这是**完全**新对我来说。感谢分享。当我找到时间时，我会阅读它。 :) – 2010-07-13 12:28:22

伟大的信息！ – 2010-07-13 13:22:17

IEEE浮点数正确地排序为_sign-magnitude整数，而不是二进制补码整数。如果你打算对负数进行排序，那么一种解决方法是补充除高位之外的每一位，而不管后者是否设置。 – user382751 2010-07-13 13:42:00

如果您想排序的算法视觉representetion，看看这个神奇的网站：

Sorting-algorithms.com

你会得到哪些最在不同情况下的感觉，但我最喜欢的是合并排序，尽管它并不比快速排序好。

来源

2010-07-13 12:13:00

理论上来说，你会比较使用big O notation的算法，它可以让你比较哪种算法对于“几乎无限”的问题会更快。实际上，在大多数情况下，这是比较算法在现实生活中表现如何的非常好的起点。

两种最流行的快速排序算法是MergeSort和快速排序。对于任何数据，合并排序保证为O（n log n），而快速排序的平均时间为O（n log n）和悲观时间O（n^2）。在实践中，大多数人使用快速排序，这是因为：

这种事几乎是在自然发生（我想你可以在地方合并排序，但它是单调乏味的，将使其更慢 - 它会增加常量隐藏在O符号） - 对于大数据集，如果数据不适合内存，这是一个问题
在大多数情况下，它在实践中速度更快
您可以稍微修改它（即取第一，中间和最后的中位数元素进行分区），这样就很难获得会使其变慢的数据。

总结我认为快速排序对于你的随机浮点数会更快，即使只看O字母看起来更糟 - 因为你会得到预期的O（n log n），并且它会有比合并更小的常量分类。

来源

2010-07-13 12:15:29 Grzenio

我看到没有人提到introsort，它通过在递归深度超过特定阈值时切换到heapsort来解决快速排序的O(n^2)最坏情况。这意味着快速排序不会有退化的机会，因为它的递归调用次数肯定会受到限制。

只要当前序列中元素的数量很少（比如说16），另一个优化就是切换到insertion sort。

这是内省排序怎么可能看：

void Introsort(int A[], int N, int left, int right, int depth) 
{ 
    if (left < right) // note: this doesn't switch to insertion sort if right - left is small enough 
    { 
     if ((1 << depth) > N) 
      Heapsort(A, left, right); 
     else 
     { 
      int P = Partition(A, left, right); 
      Introsort(A, N, left, P, depth+1); 
      Introsort(A, N, P+1, right, depth+1); 
     } 
    } 
}

此，具有良好的功能分区组合（只是随机选择的支点应该是多数已经足够了），会给你一个非常快速排序算法。

还有radix sort的选择，它的效果非常好，尤其是如果你的浮标不太大。不过，从我看到的情况来看，它需要数百万的基数才能超越内插。

来源

2010-07-13 12:36:26 IVlad

谢谢！我一定会注意到这一点。 :) – 2010-07-13 12:38:51

需要注意的一点是，如果你的任何一个集合都是nan，那么这个集合不是有序的，而且一些排序算法可能会给出意想不到的结果甚至崩溃。我认为最好的做法是确保在排序之前，您的数字都不是南。例如（使用gcc 3.4.6）将qsort（升序）应用于{2,1，nan，-1}得到{1,2，nan，-1}。

另一方面，inf和-inf不是问题。

来源

2010-07-13 13:47:13 dmuir

什么是随机浮点数的最佳排序算法？

回答

相关问题