在C++中排序並插入

我在排序時遇到了問題。我有2個功能。第一個插入一個數字到一個排序列表中，第二個接受一個未排序的列表，命名爲unsorted，創建一個新列表，並重復調用第一個列表，直到新列表成爲未排序輸入的排序版本。然後返回排序列表。在C++中排序並插入

我的理解是第一個新的列表是一個空的列表，它是一種「排序」，並逐一插入每個元素。但我的代碼不知何故不起作用。第一個功能通過了測試，但第二個功能沒有通過測試。這裏是我的代碼：

void insertInOrder(list<int>& sorted, int number) 
{ 
    if (sorted.empty()) 
     {sorted.push_back(number); 
    else 
    { 
     for(list<int>::iterator I = sorted.begin();I!= sorted.end();I++) 
     { 
      if (*I <=number) 
      { 
       sorted.insert((++I),number);// since I increases another time here 
       --I;//decrease once back 
       return; 
      } 
      else 
      { 
       sorted.insert(I,number); 
       return; 
      } 
     } 
    } 
} 

std::list<int> reorder(std::list<int>& unsorted) 
{ 
    std::list<int> ordered; 
    for (list<int>::iterator J = unsorted.begin(); J!=unsorted.end(); J++) 
    { 
     insertInOrder(ordered, *J); 
    } 

    return ordered; 
}

來源

2014-03-03 user3275943

你*有*寫排序自己呢？您不能使用例如['的std :: sort']（http://en.cppreference.com/w/cpp/algorithm/sort）？ –

這是一項家庭作業，所以... – user3275943

您的插入排序將只在索引0或索引1處插入一個新項目，因爲無論比較的結果如何，您都會在第一個循環迭代中插入它。 –

我想你想的是，如果插入值小於或等於當前的節點，然後什麼也不做，繼續循環，否則插入和回報。這當然可以寫成：如果要插入的值大於列表中的當前節點，請將其插入當前節點和退出循環之後。

所以

if (number > *I) 
{ 
    sorted.insert(++I, number); // Insert after current node 
    break;       // Exit loop 
}

來源

2014-03-03 03:29:41

我不知道爲什麼，但我的編譯器說（I + 1）是不匹配的（它給了我一個瘋狂的長錯誤信息）。那爲什麼呢？ – user3275943

@ user3275943對不起，我的錯。我忘了'std :: list'使用的迭代器不是[random access iterator]（http://en.cppreference.com/w/cpp/concept/RandomAccessIterator），而是一個[雙向迭代器]（http： //en.cppreference.com/w/cpp/concept/BidirectionalIterator），它沒有那個操作符。更新我的代碼。 –

如果我在for循環中並且在每個循環之後執行「++ I」，我應該在++ I之後執行「--I」嗎？我的意思是，額外的++會影響我的價值嗎？THx – user3275943

在C++中排序並插入

回答

相關問題