为什么这个选择排序算法仍然切换一个元素，当它已经是其他元素中最小的元素时?

Question

我正在尝试实现一个函数，该函数对 int 向量的元素进行排序，以便元素从最小的 int 变为最大的 int(例如，从 {3， 2， 1， 5} 到 {1， 2， 3， 5}(，但我不知何故无法让它按预期工作。

这是我创建的函数：

void increasingOrder(vector<int> &v)
{
vector<int>::iterator itMin = v.begin();
for (vector<int>::iterator itNew = v.begin(); itNew < v.end(); itNew++)
{
for (vector<int>::iterator it = itNew; it < v.end(); it++)
{
if (*it < *itMin)
itMin = it;
}
int temp = *itNew;
*itNew = *itMin;
*itMin = temp;
}
}

函数的预期算法基本上是这样的(选择排序(：

1. 检查所有元素
2. 选择最小的
3. 使用第一个元素切换它
4. 检查其余部分
5. 选择最小的
6. 使用第二个元素切换它
7. 重复上述步骤，直到切换每个元素。

当不需要切换元素时，问题似乎发生了，例如当参数 v = {3， 1， 2， 4} 时，结果将是 {1， 2， 4， 3}，对我来说，这似乎在不需要时仍然切换元素这样做，但我不确定哪一段代码导致了这样的错误， 谁能解释一下？

Answer 1

添加一个布尔值以了解切换是否已完成 解决您的问题：

void increasingOrder(vector<int> &v)
{
vector<int>::iterator itMin = v.begin();
for (vector<int>::iterator itNew = v.begin(); itNew < v.end(); itNew++)
{
bool isSwitched = false;
for (vector<int>::iterator it = itNew; it < v.end(); it++)
{
if (*it < *itMin)
{
itMin = it;
isSwitched = true;
}
}
if (isSwitched)
{
int temp = *itNew;
*itNew = *itMin;
*itMin = temp;
}
}
}
int main() {
vector<int> v = { 3, 1, 2, 4 };
increasingOrder(v);
}

如果没有它，即使新的 itMin 值没有更改，您仍然会切换它。