我需要一个比 O(n log n) 更快的 .Net Doubles 的稳定排序算法。
我在考虑基数排序。但是，如果我理解正确，它的性能是 O(nk)，并且由于我正在对 Doubles 进行排序，k = 8。如果 n > 2980，这只会比 O(n log n) 排序（即 QuickSort）更快。（这是正确的吗？？）在我的情况下，n 通常会在 500 或 1000 左右，但有时也会大得多。（是的，这种排序发生得非常频繁，并且基于分析分析，它的速度确实很重要）。
那么我应该坚持使用 QuickSort 还是有其他更快的选择？桶排序呢？我正在寻找 C# 或 VB.NET 中的良好实现。
编辑：我目前正在使用稳定的 QuickSort 实现。
编辑：有关浮点值，请参阅 Radix 的此实现：http: //codercorner.com/RadixSortRevisited.htm。据此，双打的 k 为 9。
事实上，doulbes 的基数排序将具有 n*k 的复杂度，其中 k 是 64 而不是 8（经典的基数排序使用数字的二进制表示）。对于任何输入，这几乎不会更快。如前所述，对于少量输入值，快速排序肯定会更快，并且还要注意 C++ 中 std::sort 的一些实现使用 O(n^2) 算法来完成少量值的排序（真的小数字），通常是插入排序（看看这里）。因此，几种算法之间的混合可能会为您提供最好的服务。
基数排序是 O(n*k)，其中 k 往往是 log(n) - 因为 k 是位数，位数随你的最高数的大小的对数而变化。
此外，查看 float 或 double 的二进制表示不太可能产生您可以排序的东西。如果您避免使用科学记数法，您可以将其转换为小数点后具有恒定位数的十进制字符串，然后进行基数排序。
您可能最好使用 .Net 排序方法（它可能已经过相当多的优化）或 timsort。
在渐近分析中，您正在查看曲线的形状，而不是它在坐标轴附近的图形上的绝对位置。这是因为，对于足够大的 n，形状比穿过轴的位置更重要。
因此，如果您不对大型列表进行排序，则最好使用较小的排序，例如快速排序甚至插入排序。
在一个紧密的循环中排序很少是一个好主意——这样的设计通常最好用堆、trap、红黑树、跳过列表、splay 树或其他 log(n) 数据结构的东西来代替。
我不认为快速排序是稳定的，尽管它可以在性能上有所损失。
mergesort 很容易编码，与 timsort 相关，并且很稳定。timsort 也很稳定。
这是一个带有支持细节的图表：
