C++ 的选择排序实现不正确

Question

对 C++ 很陌生，试图用它实例化一些基本算法。无法为选择排序返回正确的结果。这是我的代码

#include <iostream>
#include <array>
#include <vector>

using namespace std;

// Selection Sort :

int findMin(vector<int> &arr, int a)
{
    int m = a;
    for (int i = a + 1; i < arr.size(); i++)
    {
        if (arr[i] < arr[m])
        {
            m = i;
        }
        return m;
    }
}

void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void selectionSort(vector<int> &arr)
{
    if (!arr.empty())
    {
        for (int i = 0; i < arr.size(); ++i)
        {
            int min = findMin(arr, i);
            swap(arr[i], arr[min]); // Assume a correct swap function
        }
    }
}

void print(vector<int> &arr)
{
    if (!arr.empty())
    {
        for (int i = 0; i < arr.size(); i++)
        {
            cout << arr[i] << "";
            cout << endl;
        }
    }
}

int main()
{
    vector<int> sort;
    sort.push_back(2);
    sort.push_back(1);
    sort.push_back(7);
    sort.push_back(4);
    sort.push_back(5);
    sort.push_back(3);
    print(sort);
    cout << "this was unsorted array";
    cout << endl;
    cout << findMin(sort, 0);
    cout << "this was minimum";
    cout << endl;

    selectionSort(sort);
    print(sort);
}

我得到以下结果：

comparison_sort.cpp:20:1: warning: non-void function does not return a value in all control paths [-Wreturn-type]
}
^
1 warning generated.
2
1
7
4
5
3
this was unsorted array
1
this was minimum
1
2
4
5
3
0

我的问题是：是什么导致了这个控制路径错误？为什么这里的“7”要换成“0”？

提前致谢！抱歉这个菜鸟问题。

我已经检查了我当前的所有函数，似乎没有什么可以解释为什么 7 被替换为 0。我尝试了多个整数，看起来最大数字总是被替换。

Answer 1

这个警告非常真实，它也暗示了破坏您排序的问题。

您目前正在 returning m 循环体内。这意味着如果进入循环，那么函数将在第一次循环时 return m 。它只有机会检查第一个元素。

当然，如果 a 是数组的最后一个索引，那么循环将永远不会执行，您也永远不会显式 return 一个值。这是没有 return 值的“控制路径”。

很明显，您不小心将 return m; 放在了错误的位置，即使您的代码缩进很好，但某种无法解释的力量阻止您看到这一点。要解决警告和排序问题，请将 return m; 移到循环外：

int findMin(vector<int> &arr, int a)
{
    int m = a;
    for (int i = a + 1; i < arr.size(); i++)
    {
        if (arr[i] < arr[m])
        {
            m = i;
        }
    }
    return m;
}

C++ 的选择排序实现不正确

Selection Sort Implementation with C++ incorrect

c++

algorithm