选择排序循环过早停止

Question

我在试着写选择排序。一切都能工作，但是我的算法没有在整个向量_item中循环，v_sorted太短了。元素被正确地排序。

sort.hpp

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

sort.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);

sort_tests.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());
}

此测试在Collections size mismatch: 5 != 3中失败。任何测试都因尺寸不匹配而失败。循环在三次迭代后停止(在本例中)。提前谢谢你的任何线索。

Answer 1

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

将for循环更改为while循环：

while(!_item.empty()) 

现场演示

Answer 2

您正在重新实现std::min_element，如果您使用它，您不需要再次找到元素，您也不希望在它的size()上循环时更改_item的大小。

您还可以按以下方式进行排序：

template<typename T>
std::vector<T> selection_sort(std::vector<T> _item) {
    for(auto it = _item.begin(); it != _item.end(); ++it) {
        auto smallest = std::min_element(it, _item.end());
        std::iter_swap(it, smallest);
    }
    return _item;
}