这种情况下最好的排序算法是什么？

myarray = empty 
n = 10000 
range = 1000 
loop 1 to n { 
    x = random number between 1 and range 
    if x not in myarray { 
     add x to myarray 
     sort myarray 
     do something 
    } 
}

我认为插入排序，但那需要元素转移。快速排序在已排序的列表上会很糟糕。我现在能想到的最好的是Min Heap。有一些鲜为人知的排序算法更适合这种情况吗？它在C++的STL中吗？这种情况下最好的排序算法是什么？

来源

2012-01-20 user1161604

大多数快速排序实现在已排序的列表上很快。 std :: sort是为大致均匀分布的数据而设计的，就是你如何拥有它。 –

为什么你甚至在这里排序？这种情况不需要重复分类。你要添加元素，如果它不存在，只需在该循环之后对其进行排序。 – King

@King我的错误，我将添加一个做某事的行，所以我需要在每次迭代后对其进行排序。 – user1161604

您正在寻找std::set。它会在插入时对事物进行排序，并为您提供快速的“不在”操作。

来源

2012-01-20 22:58:03

最好的选择是根本不排序数组，然后等到排序结束。在一个数组中重复排序将会很昂贵，因为您将不得不通过一种方式或另一种方式切换元素。

既然你感兴趣的操作

插入元素
检查元素是否有
保持有序

你应该考虑寻找到一个不同的结构一个数组，可能是二叉搜索树，它支持快速（O（log n））插入，并可用于检索排序的顺序。

希望这会有所帮助！

来源

2012-01-20 22:58:19 templatetypedef

的最好的选择当你知道你正在排序的数字将永远是0和max_value之间是Counting sort，具有无法超越的复杂性：O(n)。

来源

2012-01-20 23:02:49 juliomalegria

或甚至对于小范围bool contains_element [范围]，contains_element [ixd]如果idx在myarray中则为true – NoSenseEtAl

这种情况下最好的排序算法是什么？

回答

相关问题