与第一次相比，为什么再次运行时此选择排序代码显示不同的输出

Question

首先，当我对这个程序进行编码时，它运行非常完美，但又运行它再次出现，它没有显示预期的输出，有人可以告诉它有什么问题吗

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    int loc,min;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < n - 1;i++){
        min = arr[i];
        for (int j = i + 1; j < n; j++)
        {
            if(min>arr[j]){
                min = arr[j];
                loc = j;
            }
            swap(arr[loc],arr[i]);
        }
    }
    for (int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

Answer 1

swap(arr[loc],arr[i]); 行应该在内部 for 循环之外，因此将其向下移动一行。此外，您需要在外部 for 循环开始时将 loc 初始化为 i。

Answer 2

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    int loc,min;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < n - 1;i++){
        min = arr[i];
        loc=i;
        for (int j = i + 1; j < n; j++)
        {
            if(min>arr[j]){
                min = arr[j];
                loc = j;
            }
            swap(arr[i],arr[loc]);
        }
    }
    for (int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

Answer 3

抛开可变长度数组不是标准 C++ 的一部分这一事实（因此使用它们的代码教程应该被销毁），代码有两个主要问题。

在一个已经排序的序列上，最里面的 if 主体永远不会被输入，因此 loc 永远不会收到确定的值。
swap放错地方了..

说明

在您的代码中...

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    int loc,min; // loc is INDETERMINATE HERE
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < n - 1;i++){
        min = arr[i];
        for (int j = i + 1; j < n; j++)
        {
            if(min>arr[j]){
                min = arr[j];
                loc = j; // loc ONLY EVER SET HERE
            }
            swap(arr[loc],arr[i]); // loc IS USED HERE EVEN IF NEVER SET
        }
    }
    for (int i = 0; i < n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

内层循环的目的是找到location (loc)的最极端值（最小，最大，无论你用什么作为你的订单标准）剩下的序列。内部循环中不应发生交换，初始极值位置（同样，loc）应该是 outer 循环的当前索引（在本例中 i)

因此...

我们不需要 min。没意义。
进入内循环前，我们必须初始化loc为i。
我们在内部循环之后交换，然后只有当 loc 不再是 i.

结果是这样的。

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    for (int i = 0; i < n - 1; i++)
    {
        int loc = i;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[loc] > arr[j])
                loc = j; // update location to new most-extreme value
        }

        // only need to swap if the location is no longer same as i
        if (loc != i)
            swap(arr[loc], arr[i]);
    }
    
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

与第一次相比，为什么再次运行时此选择排序代码显示不同的输出

Why does this selection sort code shows different output when running again as compared to first time

c++

g++

selection-sort

与第一次相比，为什么再次 运行 时此选择排序代码显示不同的输出

Why does this selection sort code shows different output when running again as compared to first time

c++

g++

selection-sort

与第一次相比，为什么再次运行时此选择排序代码显示不同的输出