使用向量的插入排序，不起作用

Question

我试图创建一个使用向量的插入排序算法，但我没有从数组的开头解析元素（此处为向量），而是尝试从末尾开始解析。代码只是第一次对元素进行排序，并删除了我的向量的第一个元素。我想知道我可以对我的代码进行哪些更正才能使其正常工作。基本程序：

从元素开始到最后（倒数第二个元素）
将其插入'sorted'子数组（向量）中的正确位置
从初始位置删除它
继续算法，向后遍历直到向量的开头

代码：

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T> &ar){
    //start from second last element upto first element
    for(auto i = ar.end()-2; i >= ar.begin(); i--){
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while(j != ar.end() && *i < *j) j++;
        //insert the insertion element at final position of the pointer
        ar.insert(j,*i);
        //erase the original element
        ar.erase(i);
    }
}
template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,1,6};
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}

预期输出：

6 1 7 1 3 2 6723 4 1 6 
1 1 1 2 3 4 6 6 7 6723

获得的输出：

6 1 7 1 3 2 6723 4 1 6 
1 7 1 3 2 6723 4 1 6 1

Answer 1

这是我对插入反向算法的实现。

template <class T>
void isort(vector <T> &ar){
    if(ar.size() < 2)
        return;
    //start from second last element upto first element
    for(auto i = ar.end()-2; i >= ar.begin(); i--){

        auto j = i;
        //swap values until condition met
        while((j + 1) != ar.end() && *(j + 1) < *j) {
            //swap values
            auto tmp = *j;
            *j = *(j + 1);
            *(j + 1) = tmp;
            ++j;
        }
    }
}

这里的不同之处在于它交换了两个值而不是 insert/erase。

while(j != ar.end() && *i < *j) j++;
//insert the insertion element at final position of the pointer
ar.insert(j,*i);
//erase the original element
ar.erase(i);

Answer 2

关于你的方法，所以我根据你的解决方案修改了你的代码，现在可以了。性能可能比交换更差，只是因为 vector 在 insert/erase.

之后移动元素

#include <iostream>
#include <vector>
using namespace std;

template <class T>
void isort(vector <T>& ar) {
    if (ar.size() < 2)
        return;

    //start from second last element upto first element
    auto i = ar.end() - 2;
    do
    {
        //iterator pointing towards element next to insertion element
        auto j = i + 1;
        //traverse and increase the pointer until condition met
        while (j != ar.end() && *i > *j) ++j;
        //insert the insertion element at final position of the pointer

        if (*(j - 1) < *i && (j - 1) != i) {
            ar.insert(j, *i);
            i = ar.erase(i);
        }

        if (i == ar.begin())
            break;
        --i;
    } while (true);
}

template <class T>
void display(vector <T> &ar){
    for(auto i = ar.begin(); i != ar.end(); i++){
        cout << *i << ' ';
    }
    cout << endl;
}
int main() {
    vector <int> X {6,1,7,1,3,2,6723,4,6,1};
    X.reserve(X.size() * 2);
    display <int>(X);
    isort <int>(X);
    display <int>(X);
}

使用向量的插入排序，不起作用

Insertion sort using vectors, not working

c++

sorting

vector

insertion-sort