将元素插入已排序的向量中

Question

我编写了一个C++程序，目的是将元素快速插入到已排序的向量中。它有时但并非全部都有效，我一直无法弄清楚原因。当我用纸和铅笔执行算法时，算出来了，但有些问题是错误的。请帮忙？

#include <time.h> 
#include <cstdlib> 
#include <vector> 
#include <iostream> 
using namespace std; 

vector<int> sortedVec; 

int main() { 
    // Random seed 
    srand(time(NULL)); 

    // Put in n random elements 
    for (int i = 0; i < 10; i++) sortedVec.push_back(rand()%10); 

    // Sort the vector 
    bool swapped = true; 
    int endDecrement = 0; 
    while (swapped) { 
     swapped = false; 
     endDecrement++; 
     for (int i = 0; i < sortedVec.size()-endDecrement; i++) { 
      if (sortedVec.at(i) > sortedVec.at(i+1)) { 
       int swap = sortedVec.at(i); 
       sortedVec.at(i) = sortedVec.at(i+1); 
       sortedVec.at(i+1) = swap; 
       swapped = true; 
      } 
     } 
    } 

    cout<<"Sorted random list:"<<endl; 
    for (int i = 0; i < sortedVec.size(); i++) cout<<sortedVec.at(i)<<endl; 

    int toInsert = rand()%10; 
    cout<<"Random element to insert = "<<toInsert<<endl; 

    // Insert a random int to the sorted vector 
    int minIndex = 0; 
    int maxIndex = sortedVec.size()-1; 
    while (true) { 
     int mid = (maxIndex-minIndex)>>1; 
     if (toInsert == sortedVec.at(mid) || maxIndex-minIndex < 2) { 
      sortedVec.insert(sortedVec.begin()+mid, toInsert); 
      break; 
     } 
     else if (toInsert < sortedVec.at(mid)) maxIndex = mid; 
     else if (toInsert > sortedVec.at(mid)) minIndex = mid; 
    } 

    cout<<"Random list with inserted element:"<<endl; 
    for (int i = 0; i < sortedVec.size(); i++) cout<<sortedVec.at(i)<<endl; 

    return 0; 
} 

Answer 1

我改变它，我敢肯定，它在现在的所有情况：

if (toInsert < sortedVec.at(0)) sortedVec.insert(sortedVec.begin(), toInsert); 
else if (toInsert > sortedVec.at(sortedVec.size()-1)) sortedVec.push_back(toInsert); 
else { 
    int minIndex = 0; 
    int maxIndex = sortedVec.size(); 
    while (true) { 
     int mid = (maxIndex+minIndex)>>1; 
     if (toInsert == sortedVec.at(mid) || maxIndex-minIndex < 2) { 
      sortedVec.insert(sortedVec.begin()+mid+1, toInsert); 
      break; 
     } 
     else if (toInsert < sortedVec.at(mid)) maxIndex = mid; 
     else if (toInsert > sortedVec.at(mid)) minIndex = mid; 
    } 
} 

@LeGEC和@chac，感谢您寻找到我张贴的算法，它帮助了很多。 @Jerry Coffin，我没有得到std :: upper_bound来为此工作，但不是为我的Node类的一个变量，尽管如此，谢谢你。

Answer 2

正如评论指出的那样，你提出的是要解决的一个基本问题一个颇为曲折的方式。

你的问题可能更具吸引力随机生成初始化与导致所观察到的行为来调试一个常数代替time(NULL)。

不这样做，我会放在罪魁祸首出价：

int maxIndex = sortedVec.size()-1; 

我想应该是

int maxIndex = sortedVec.size(); 

，或者你从来不考虑顶层元素。

Answer 3

有标准库设施进行排序：

#include <algorithm> 
#include <vector> 

template <typename T, typename A, typename C> 
class SortedVector { 
public: 
    SortedVector() {} 

    // Initialization 
    template <typename It> 
    SortedVector(It begin, It end): _data(begin, end) { 
     std::sort(_data.begin(), _data.end(), _comparator); 

     // if we wanted unicity 
     _data.erase(std::unique(_data.begin(), _data.end(), _comparator), _data.end()); 
    } 

    // Addition of element (without checking for unicity) 
    void add(T const& element) { 
     _data.push_back(element); 
     std::inplace_merge(_data.begin(), prev(_data.end()), _data.end(), _comparator); 
     // or simply: std::sort(_data.begin(), _data.end(), _comparator); 
     // it is surprisingly efficient actually because most sort implementations 
     // account for partially sorted range. It is not, however, stable. 
    } 

    // Addition of element with unicity check 
    bool add(T const& element) { 
     typename std::vector<T, A>::iterator it = 
      std::lower_bound(_data.begin(), _data.end(), element, _comparator); 
     if (it != _data.end() and not _comparator(element, *it)) { 
      return false; 
     } 
     size_t const n = it - _data.begin(); 

     _data.push_back(element); 
     std::copy(_data.begin() + n, _data.end() - 1, _data.begin() + n + 1); 
     // C++11: std::move 
     _data[n] = element; 
    } 

private: 
    std::vector<T, A> _data; 
    C _comparator; 
}; 

Answer 4

我写了一个C++程序与迅速将元素插入一个有序vector

你不应该这样做，我们的目标。 std :: vector不适合快速插入到自定义位置。 编辑：顺便说一句你正在做替换，而不是插入。对于矢量的使用是可以的。

此外，您的代码患有不使用标准功能。 std :: sort，如果你真的想手动交换元素，你也有std :: swap。

而且这是不必要的：

int mid = (maxIndex-minIndex)>>1; 

编译器能够并确实容易地优化/ 2到>> 1;

编辑：

您的代码被打破，这将有望告诉你为什么： http://ideone.com/pV5oW

Answer 5

基础上的评论，让我们假设我们有一个结构是这样的：

struct data { 
    int fval; 
    // other stuff we don't care about right now 
}; 

而且，我们假定我们有这些向量：

std::vector<data> items; 

如果我们想在顺序中插入一个新的项目，我们不要真的想做一个二进制搜索，然后std::insert。这需要O（日志N）搜索，然后是O（N）插入。相反，我们可以将两者结合起来，所以我们只需要一个O（N）操作来找到正确的位置并进行插入。这里有一个简单的版本：

void insert(std::vector<int> &vec, int new_val) { 
    if (vec.empty()) { 
     vec.push_back(new_val); 
     return; 
    } 

    vec.resize(vec.size()+1); 
    std::vector<int>::reverse_iterator pos = vec.rbegin(); 

    for (; *(pos+1) > new_val && (pos+1) != vec.rend(); ++pos) 
     *pos = *(pos+1); 
    *pos = new_val; 
} 

在你的情况，你要插入一个data结构，并且比较(pos+1)->fval > new_val.fval，但其基本思想是，否则几乎是相同的。实际上，这个应该是可能被实现为一个通用算法，但我现在没有时间。