一组随机浮点数的最佳排序算法是什么？
我的一位同事今天下午把这个问题悬在空中，让我感到好奇。 我精通排序algos，但缺乏compsci / compeng的正式学位（我不喜欢承认），不能真正指责这一点。 ：p
哦，是的，这在C＃/ .NET实现的上下文中是温和的…以防万一改变了一些事情。
多谢你们。 🙂
对于固定长度的数字，您不限于基于比较的排序算法，因此O(n*log(n)) 不是限制。 Radix Sort在O(n) ，并且可以非常方便地使用，因为当它们的位模式被解释为整数时，IEEE 754浮点数的惊人属性被正确排序。
我看到没有人提到过introsort ，它通过在递归深度超过某个阈值时切换到heapsort来解决快速排序的O(n^2)最坏情况。 这意味着快速排序不会有机会退化，因为它的递归调用次数肯定会受到限制。
另一个优化是，只要您当前所在序列的元素数量很少（例如16），就切换到插入排序 。
这就是introsort的样子：
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); } } }
这个，结合良好的分区function（简单地随机选择枢轴应该足以满足大多数目的），将为您提供一个非常快速的排序算法。
也有基数排序的选择，这非常有效，特别是如果您的花车不是太大。 从我所看到的情况来看，基数排序需要数百万个元素才能超越内省。
如果您想要对排序算法进行直观表示，请查看这个梦幻般的网站：
Sorting-algorithms.com
你会得到在不同情况下效果最好的感觉，但我最喜欢的是合并排序，即使它不比快速排序好多了。
从理论上讲，您使用大O表示法比较算法，这可以让您比较哪种算法对于“几乎无限”的问题更快。 在大多数情况下，在实践中，这是比较算法在现实生活中的表现的一个非常好的注意点。
两种最流行的快速排序算法是MergeSort和快速排序。 对于任何数据，合并排序保证为O（n log n），而快速排序的平均时间为O（n log n）和悲观时间O（n ^ 2）。 在实践中，大多数人使用快速排序，因为：
- 它自然发生在几乎就位（我认为你可以使合并排序到位，但它很繁琐，会使它变慢 – 它会增加隐藏在O表示法中的常量） – 对于大数据集这是一个问题，如果数据确实存在不适合记忆
- 在大多数情况下，它在实践中更快
- 你可以稍微修改它（即取第一个，中间和最后一个元素的中位数进行分区），这样就很难获得使它变慢的数据
总而言之，我认为快速排序对于你的随机浮点数会更快，即使只看O符号看起来更糟糕 – 因为你将得到预期的O（n log n）并且它将具有比合并排序更小的常量。
需要注意的一个小问题是，如果你的任何一个集合是nan，则该集合不是有序的，并且一些排序算法可能会产生意外结果甚至崩溃。 在排序之前，我认为最好确保你的数字都没有。
例如（使用gcc 3.4.6）将qsort（升序）应用于{2,1，nan，-1}给出{1,2，nan，-1}。
另一方面，inf和-inf不是问题。