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

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。它会在您插入时对内容进行排序，并为您提供快速的“不在”操作。