插入排序与插入/擦除?(所以我需要对一个向量进行排序，而不是手工做事，而是使用插入和擦除

Question

所以我需要对一个向量进行排序，而不是手动做事，而是使用插入和擦除。

到目前为止，我的代码是

for (int x = 0; x < arr.size(); x++) {
     for (int y = x; y < arr.size(); y++)
     {
            if ( arr[y] < arr[x])
            {
                arr.insert(arr.begin()+x,arr[y]);
                arr.erase(arr.begin()+y+1);
            }     
     }
}

然而，当它运行时，我的测试用例超时并适用于其中的 3 个(测试用例是 245+ 长数整数(。我必须使用向量，并且必须使用插入排序作为设计的一部分(找到要排序的最小交换，但从这里开始削减(，我知道它的运行时很差。

我在这里做错了什么让编译器这样做？

Answer 1

每次调用arr.insert或arr.erase时，您都会得到O(n(复杂性。尝试改用std::swap (arr[x], arr[y])。