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

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，但其基本思想是，否則幾乎是相同的。實際上，這個應該是可能被實現爲一個通用算法，但我現在沒有時間。