奇怪的插入排序运行次

Question

我正在尝试使用插入排序对向量进行排序，但对于大多数值，它无法完成。如果向量大小大于 3，则循环将在很长一段时间内不会完成，根本不会完成，或者它将按预期快速完成，直到随机值达到 5。

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <vector>

void PRINT(std::vector<int> &data);


void insertion(std::vector<int> data, clock_t Time);

int main()
{
    clock_t Time;
    int dataSize, maxval;
    std::vector<int> data;

    srand(time(0));


    std::cout<<"input vector size\n";
    std::cin>>dataSize;
    std::cout<<"input max value\n";
    std::cin>>maxval;

    Time=clock();
    for(int i=0; i<dataSize; i++)
    {
        data.push_back(1+rand()%maxval);
    }
    Time=clock()-Time;
    std::cout<<"ticks to randomize "<<Time<<" seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl;

    insertion(data, Time);
    return 0;
}

void PRINT(std::vector<int> &data)
{   
    std::cout<<"data contains: ";
    for(int i=0; i<data.size(); i++)
    std::cout<<data[i]<<", ";
    std::cout<<std::endl;
}


void insertion(std::vector<int> data, clock_t Time)
{
    bool sorted;    
    std::vector<int>::iterator j;

    Time=clock();
    for(int i=1; i<data.size(); i++)
    {   
        j=(data.begin()+i-1);
        sorted=false;

        while(!(j==data.begin())&&!sorted)
        {
            if (*j<data[i])
            {
                sorted=true;
                data.insert((j+1),data.at(i));
            }

            j--;
        }

    }
    Time=clock()-Time;

    std::cout<<"insertion:\nticks taken "<<Time<<"\n";
    std::cout<<"seconds "<<float(Time)/CLOCKS_PER_SEC<<std::endl;
    PRINT(data);
}

有人明白为什么我的实现在更高的值下有如此疯狂的运行时间吗？有没有更好的方法来实现这个？

Answer 1

这是一个明显的错误。

std::vector<int>::iterator j;
//...
for (int i = 1; i < data.size(); i++)
{
    j = (data.begin() + i - 1);  // iterator j points to a location in the vector
    //...
    while (!(j == data.begin()) && !sorted)
    {
       //...
       data.insert((j + 1), data.at(i));   // vector being resized here
     }
     j--;  // this iterator is now invalidated!

问题是您在循环中间更改向量的大小，并且指向向量内部的 j 迭代器由于调整向量大小而变得无效。您尝试递减无效的迭代器，一切都从那里分崩离析（Visual Studio 中的运行显示迭代器是 "not decrementable" 的调试消息框）。

要么使用使用整数（不是迭代器）的直接索引，要么使用我关于实现插入排序的评论中 link 中显示的技术。

奇怪的插入排序运行次

insertion sort bizzare run time

c++

loops

vector

runtime

insertion-sort

奇怪的插入排序 运行 次

insertion sort bizzare run time

c++

loops

vector

runtime

insertion-sort

奇怪的插入排序运行次