我需要一个稳定的 .Net Double 排序算法，该算法比 O(n log n) 更快。
我正在考虑基数排序。但是，如果我理解正确的话，它的性能是 O(n k) 并且因为我对 Double 进行排序，k = 8。如果 n > 2980，这只会比 O(n log n) 排序(即 QuickSort)更快。(这是正确的吗？)在我的例子中，n 通常会在 500 或 1000 左右，但有时也会大得多。 (是的，这种排序非常频繁地进行，并且基于概要分析，其速度确实很重要)。
那么我应该坚持使用 QuickSort 还是有其他更快的替代方案？桶排序怎么样？我正在寻找 C# 或 VB.NET 中的良好实现。
编辑:我目前正在使用稳定的 QuickSort 实现。
编辑:请参阅浮点值的 Radix 实现:http://codercorner.com/RadixSortRevisited.htm 。据此， double 的 k 将为 9。
最佳答案
事实上，doulbes 的基数排序的复杂度为 n*k，其中 k 是 64 而不是 8(经典的基数排序使用数字的二进制表示)。对于任何输入来说这都不会更快。正如已经说过的，对于少量输入值，快速排序肯定会更快，并且还要注意，C++ 中 std::sort 的一些实现使用 O(n^2) 算法来完成少量值的排序(实际上小数字)，通常是插入排序(看看 here )。因此，也许多种算法的混合最适合您。
关于.net - .Net 有没有比 O(n log n) 更快的稳定排序算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10322036/