stl实现插入排序的有关问题

stl实现插入排序的问题

C/C++ code

template <class T> void InsertSort(vector<T>& v) //插入排序{    vector<T> temp;    typedef vector<T>::iterator VI;    temp.push_back(v[0]);        for (VI i = v.begin()+1;i<v.end();++i)    {                for (VI j = temp.end()-1;j>=temp.begin();--j)        {                    if ((*i)>=(*j))            {                temp.insert(j+1,(*i));                break;            }            if (j==temp.begin()&&(*i)<(*j))            {                temp.insert(temp.begin(),(*i));//[color=#800000]问题应该在这里 但是不知道啥问题[/color]            }        }    }    v=temp;}

很简单的插入排序 但是找了好久都没找到 请各位看看

[解决办法]
for (VI j = temp.end()-1;j>=temp.begin();--j)
//这一句，迭代器失效在插入之后
[解决办法]

temp.insert(temp.begin(),(*i));//问题应该在这里 但是不知道啥问题

一句后面break好像可以。。。
[解决办法]
for (VI j = temp.end()-1;j>=temp.begin();--j)
跳出这个循环的条件是 j<temp.begin()而不是j等于temp.begin(),也就是说j指向了temp.begin()的前一个位置才跳出循环 

if (j==temp.begin()&&(*i)<(*j))
这一句有问题，j有可能不等于temp.begin()而是指向了temp.begin()的前一个位置
将这一句更改为：if (j==temp.begin()-1&&(*i)<(*（j-1))）

[解决办法]
不要在stl不熟练的情况下，复用vector。加一个vector的临时变量来存储中间过程。
[解决办法]

探讨

引用:

是啊 加个break就行了 这个break有啥意义呢？

[解决办法]
j指向begin的前一个位置的时候不就退出循环了吗？ 所以我觉得这里指不到啊 ！而且在if (j==temp.begin()&&(*i)<(*j)) 这句话后面加一个break就可以了，我觉得是不是如果不加break 就会使j=begin()-1 从而产生非法指针？

j =begin() - 1;不会产生非法指针的，况且j根本就不是指针是一个迭代器，迭代器和指针是不一样的，唉，楼主你要多看看书啊，因为vector容器允许它的迭代器进行算术运算，也允许迭代器指向第一个元素的前一个位置
[解决办法]

C/C++ code

if (j==temp.begin()&&(*i)<(*j))            {                temp.insert(temp.begin(),(*i));//[color=#800000]问题应该在这里 但是不知道啥问题[/color]break;//在这里加个break就可以了            }
[解决办法]
如果你不在temp.insert(temp.begin(),(*i));这条语句后加break的话，执行完插入语句后，迭代器j就失效了，不再执向temp.begin()了，而程序会继续执行下一句，也就是下面这一句：
for (VI j = temp.end()-1;j>=temp.begin();--j)；会继续对j进行--j;操作，然而当前迭代器j已经失效了，再对j进行前自减操作是非法的，会发生运行时错误，程序崩溃
 

 

查看更多 下一篇