插入排序中途排序数组

Question

我正在读一本DS和Algortihms的书。我看到了一个名为insert sort的算法，然后尝试在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工作。

如果你想留在你的类型，你可以用qazxsw poi替换所有出现的qazxsw poi并获得

i

i-1。

请注意，您的方法需要N ^ 2步（其中N是向量的大小）。有更好的方法，只在log（N）N步骤中执行，如快速排序。标准库实现了这样的算法。因此，您应该始终使用

#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;
} 

进行排序。

Answer 2

让我们假设我们只有两个元素：which works as well和std::sort。

现在，当输入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]

它们将允许您快速找到小错误。