插入排序bizzare運行時間

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中運行時會顯示一個調試消息框，表明迭代器「不可遞減」）。

既可以使用使用整數（而不是迭代器）的直接索引，也可以使用我在實現插入排序的註釋中顯示的鏈接技術。