使用递归的选择排序

Question

void swap(int a[], int x, int y)
{

    int temp = a[x];
    a[x] = a[y];
    a[y] = temp;
}
void sort(int arr[], int x)
{
    static int count = 0;
    if (x == 1)
    {
        return;
    }
    int min = 100;    //  random value
    int index;
    for (int i = 0; i < x; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
            index = i;
        }
    }
    swap(arr, count, index);
    count++;
    sort(arr + 1, x - 1);
}
int main()
{
    int x;
    cin >> x;
    int A[x];
    for (int i = 0; i < x; i++)
    {
        cin >> A[i];
    }
    sort(A, x);
    for (int i = 0; i < x; i++)
    {
        cout << A[i] << " ";
    }
    cout << endl;
    return 0;
}

这段代码是使用递归的选择排序。它正在打印垃圾值。这有什么错误。我不确定，但我猜是因为在排序函数 () 中使用了静态变量。它正在打印垃圾值

Answer 1

将swap(arr, count, index);替换为

swap(arr, 0, index);

并删除 static int count = 0;.

将主体中的sort(A, x);替换为

sort(A, x - 1);

并将条件if (x == 1)更改为if (x == 0)。

我建议将 index 重命名为 last。

用

替换min = 100;

min = arr[0];

Answer 2

对于像这样的初学者可变长度数组

int x;
cin >> x;
int A[x];

不是标准的 C++ 功能。

然而，当例如使用等于 0.

的第二个参数调用时，该函数可以调用未定义的行为

声明静态变量也没有意义。

该函数不会对值大于 100 的数组元素进行排序。

变量index必须在for循环之前初始化为0。

另外已经有交换两个对象的标准函数std::swap。

函数可以这样定义

#include <algorithm>

void selection_sort( int a[], size_t n )
{
    if ( not ( n < 2 ) )
    {
        auto it = std::min_element( a, a + n );

        if ( it != a ) std::iter_swap( a, it );

        selection_sort( a + 1, n - 1 );
    }
}

如果您还不知道标准算法，那么函数可以看下面的方式

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

void selection_sort( int a[], size_t n )
{
    if ( not ( n < 2 ) )
    {
        size_t index = 0;

        for ( size_t i = 1; i < n; i++ )
        {
            if ( a[i] < a[index] ) index = i;
        }

        if ( index != 0 ) swap( a[0], a[index] );  

        selection_sort( a + 1, n - 1 );
    }
}

使用递归的选择排序

selection sort using recursion

c++

sorting

recursion

selection-sort

function-definition