.net - 是否有比 O(n log n) 更快的 .Net Doubles 稳定排序算法？

Question

我需要一个 稳定 的 .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。

Answer 1

事实上，双倍基数排序的复杂度为 n*k，其中 k 是 64 而不是 8(经典基数排序使用数字的二进制表示)。对于任何输入，这都不会更快。如前所述，对于少量输入值，快速排序肯定会更快，并且还要注意 C++ 中 std::sort 的某些实现使用 O(n^2) 算法来完成少量值的排序(实际上小数字)，通常是插入排序(看看 here )。因此，也许几种算法之间的混合会为您提供最好的服务。