插入排序将数组排序到一半

Question

我正在读一本DS和Algortihms的书。我看到了一种名为插入排序的算法，然后尝试在 C++ 中应用它。当我对数组进行排序时，数组的第一个元素保留在它之前所在的位置，而其他元素则转到它们适当的位置！我不明白发生了什么事。我的代码：

#include<iostream>
#include<vector>

using namespace std;

void vec_in(vector<unsigned>& vec, unsigned size);
void vec_out(vector<unsigned> vec);

int main(){
    vector<unsigned> vec;
    unsigned size;
    cout<<"SIZE : ";
    cin>>size;
    cout<<"ARRAY : ";
    vec_in(vec,size);
    cout<<endl;
    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];
        unsigned i=j-1;
        cout<<key<<endl;
        while(i>0&&vec[i]>key){
            vec[i+1]=vec[i];
            i--;
        }
        vec[i+1]=key;
    }
    cout<<"SORTED ARRAY : ";
    vec_out(vec);

} 

void vec_in(vector<unsigned>& vec, unsigned size){
    for(unsigned i=0; i<size; i++){
        unsigned in;
        cin>>in;
        vec.push_back(in);
    }
    cout<<endl;
}
void vec_out(vector<unsigned> vec){
    for(unsigned i=0; i<vec.size(); i++){ 
        cout<<vec[i]<<" ";
    } 
    cout<<endl;
}

我用许多示例尝试了此代码，结果仍然相同：第一个元素从未排序。

Answer 1

您应该将 while(i>0&&vec[i]>key){ 替换为 while(i>=0&&vec[i]>key){。在这种情况下 i 可以得到负值。因此，它需要被烧焦，即 this code 有效。

如果你想保留你的类型，你可以用 i-1 替换所有出现的 i 并获得

#include<iostream>
#include<vector>

using namespace std;

void vec_in(vector<unsigned>& vec, unsigned size);
void vec_out(vector<unsigned> vec);

int main(){
    vector<unsigned> vec;
    unsigned size;
    cout<<"SIZE : ";
    cin>>size;
    cout<<"ARRAY : ";
    vec_in(vec,size);
    cout<<endl;
    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];
        unsigned i=j;
        cout<<key<<endl;
        while(i>0&&vec[i-1]>key){
            vec[i]=vec[i-1];
            i--;
        }
        vec[i]=key;
    }
    cout<<"SORTED ARRAY : ";
    vec_out(vec);

} 

void vec_in(vector<unsigned>& vec, unsigned size){
    for(unsigned i=0; i<size; i++){
        unsigned in;
        cin>>in;
        vec.push_back(in);
    }
    cout<<endl;
}
void vec_out(vector<unsigned> vec){
    for(unsigned i=0; i<vec.size(); i++){ 
        cout<<vec[i]<<" ";
    } 
    cout<<endl;
}

which works as well.

请注意，您的方法需要 N^2 个步骤（其中 N 是向量的大小）。有更好的方法，只需 log(N) N 步即可完成，例如快速排序。标准库实现了这样的算法。因此，您应该始终使用std::sort进行排序。

Answer 2

假设我们只有两个元素：4 和 3。

现在，当进入 for 循环时会发生什么。

    for(unsigned j=1; j<size; j++){
        unsigned key = vec[j];         /* key := 3      */
        unsigned i=j;                  /* i := 1        */
        cout<<key<<endl;               /* print(3)      */
        while(i>0&&vec[i-1]>key){      /* i > 0 (false) */
            vec[i]=vec[i-1];
            i--;
        }
        vec[i]=key;
    }

没有进入做排序的while循环。尝试比较 vec[0] 和 vec[1].

时总会发生这种情况

根据经验，请首先进行以下测试：

1) empty vector
2) vector with one element
3) vector with two elements a) sorted acending b) sorted descending
...

它们可以让您快速找到小错误。

插入排序将数组排序到一半

Insertion Sort sorts array halfway

c++

algorithm

sorting

insertion-sort