c++ - 用 vector 实现选择排序

Question

我正在尝试实现一个使用选择排序对随机生成的 vector 进行排序的函数。我正在尝试一种天真的方法，只是为了看看我是否能让它正常工作。这是我的尝试:

void selection_sort(std::vector<int>& v)
{
    int pos, min, i;
    //std::vector<int>::iterator pos, min, i;

    for( pos = v[0]; pos < v[30]; ++pos)
    {
        min = pos;

        for( i = v[pos + 1]; i < v[30]; ++i)
        {   
            if( i < min)
            {
                min = i;
            }
        }

        if( min != pos)
        {   
            std::swap(v.at(min), v.at(pos));

        }
    }
}

但是由于某种原因，当我再次显示 vector 时，所有元素的顺序与它们原来的顺序完全相同。我不确定我是否没有正确使用 std::swap 或者我的选择排序是否写得不正确。我相信答案很简单，但我看不到。提前感谢您的帮助。

Answer 1

您的问题是您试图将循环基于 vector 中的实际值，而不是 vector 中的索引。

所以如果你的 vector 是随机生成的，你这样说:

for( pos = v[0]; pos < v[30]; ++pos)

v[0] 处的值有可能大于 v[30]。因此循环永远不会运行。我在这个循环中看到同样的问题:

for( i = v[pos + 1]; i < v[30]; ++i)

所以我建议在实际循环中使用索引。尝试类似的东西:

for( pos = 0; pos < 30; ++pos)
{
  min = v[pos];

等...

编辑:如下所述，最好将 vector 的大小作为循环的基础。但是，为了避免每次循环运行时都调用昂贵的 size() 方法，只需在循环开始之前获取大小。例如:

size_t size = v.size();
for(size_t pos = 0; pos < size; ++pos)