c++ - 选择排序 - 循环停止得太早

Question

我正在尝试编写选择排序。一切正常，但我的算法没有遍历整个 vector _item 使我的 v_sorted 太短。元素排序正确。

排序.hpp

template<typename T>
std::vector<T> selection_sort(std::vector<T>);

排序.cpp

template<typename T>
std::vector<T> selection_sort(std::vector<T> _item) {
    std::vector<T> v_sorted;
    for(int i = 0; i < _item.size(); ++i) {
        T smallest = _item[0];
        for(auto const& j : _item) {
            if(j < smallest) {
                smallest = j;
            }
        }
        v_sorted.push_back(smallest);

        auto it = std::find(_item.begin(), _item.end(), smallest);
        if (it != _item.end()) {
            // to prevent moving all of items in vector
            // https://stackoverflow.com/a/15998752
            std::swap(*it, _item.back());
            _item.pop_back();
        }
    }
    return v_sorted;
}

template std::vector<int> selection_sort(std::vector<int> _item);

排序测试.hpp

BOOST_AUTO_TEST_CASE(selection_sort_int)
{
    std::vector<int> v_unsorted = {3, 1, 2, 7, 6};
    std::vector<int> v_sorted = {1, 2, 3, 6, 7};
    auto v_test = exl::selection_sort(v_unsorted);
    BOOST_CHECK_EQUAL_COLLECTIONS(v_sorted.begin(), v_sorted.end(), 
                                  v_test.begin(), v_test.end());
}

此测试失败，集合大小不匹配:5 != 3。任何测试都因大小不匹配而失败。循环在三次迭代后停止(在本例中)。提前感谢您提供任何线索。

Answer 1

for 循环的 ++i 和 _item.pop_back() 的同时效果具有递增两次的效果，而您只想递增一次。

将 for 循环更改为 while 循环:

while(!_item.empty()) 

Live Demo