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

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.它会在您插入时对事物进行排序,并为您提供快速"不在"操作.