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

Question

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中吗？

Answer 1

你在找std::set。它在你插入的时候保持排序，并给你一个快速的“不在”操作。

Answer 2

当您知道要排序的数字总是在0和max_value之间时，最好的选择是，它具有无与伦比的复杂性：O(n)。

Answer 3

最好的选择是根本不对数组排序，然后等到最后再排序。在数组中重复排序的代价很高，因为您必须以这种方式或另一种方式移动元素。

既然你对这些操作感兴趣

• Insert an element
• Check if an element is
• Maintain order

(检查元素是否存在并维护排序顺序)

您应该考虑查看与数组不同的结构，可能是二进制搜索树，它支持快速(O(log ))插入，并可用于检索排序的顺序。

希望这能有所帮助！