对于一组随机浮点数,最好的排序算法是什么?

对于固定长度的数字,您不局限于基于比较的排序算法,所以 O(n*log(n)) 是 极限。 Radix Sort 工作地点 O(n) ,并且可以非常方便地使用,因为ieee754浮点的惊人特性是,当它们的位模式被解释为整数时,可以正确地排序。

introsort ,解决了快速排序问题 O(n^2) 最坏的情况是切换到 heapsort 当递归深度超过某个阈值时。这意味着快速排序将不会有退化的机会,因为它的递归调用数肯定是有限的。

insertion sort 当你当前所在序列的元素数很小时(比如说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);
        }
    }
}

还有一个选择 radix sort

如果你想在排序算法上有一个直观的表现,请访问这个奇妙的网站:

Sorting-algorithms.com

你会觉得在不同的情况下,合并排序效果最好,但我最喜欢的是合并排序,尽管它并不比快速排序好多少。

从理论上讲,您可以使用 big O notation ,它让您比较哪种算法对“几乎无限”问题更快。在实践中,在大多数情况下,这是一个非常好的起点来比较算法在现实生活中的表现。

1. 它几乎是自然发生的(我认为您可以就地进行合并排序,但这很乏味,而且会使它变慢—它会增加隐藏在O表示法中的常量)—对于大型数据集,如果数据不适合内存,这是一个问题
2. 在大多数情况下,它在实践中更快
3. 您可以稍微修改它(即取第一个、中间个和最后一个元素的中间值进行分区),这样就很难获得速度较慢的数据

总而言之,我认为快速排序对于随机浮点数来说会更快,尽管只看O表示法似乎更糟——因为您将得到预期的O(n logn),并且它的常量将小于合并排序。

需要注意的一点是,如果您的集合中有任何一个是nan,则该集合没有排序,某些排序算法可能会给出意外的结果,甚至崩溃。 我认为在分类之前最好确保你的数字都不是nan。

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