递归选择排序在 C 中输出不正确的值

Question

我一直在研究选择排序的递归版本。 MaxInd 在 SelectionSort 的一次迭代中运行良好，但是一旦我使 SelectionSort 递归，MaxInd 在 SelectionSort 的第一次迭代后开始产生不正确的值，这导致我的代码交换不正确的值。我不确定为什么要这样做。

#include <stdio.h>

int MaxInd(int arr[], int i, int len, int max, int index){
    if (arr[i]>max){
        max=arr[i];
        index=i;
    }
    if(i==len)
        return index;

    index = MaxInd(arr,i+1,len,max,index);
    return index;
}
void SelectionSort(int arr[], int len){
    int index=0; int max=0; int i=0; int temp=0; int num=0;
    if(len<0){
        for(int j=0; j<6; j++)
            printf("array=%d\n",arr[j]);
            return;
    }
    num = MaxInd(arr, i, len, max, index);
    if(len>0){
        temp=arr[len-1];
        arr[len-1]=arr[num];
        arr[num]=temp;
    for(int j=0; j<6; j++)
            printf("%d ",arr[j]);
        printf("\n");
    }
    return SelectionSort(arr,len-1);
}
int main(void){
    int arr[6] = {1,4,3,7,9,2};
    int len=sizeof(arr)/sizeof(arr[0]);
    SelectionSort(arr, len);
}

Answer 1

处理return语句的正确方法是这样写

return SelectionSort(arr,len-1);

您应该从函数中 return 一个 int - 但您没有放置任何 return 语句 - 然后您再次尝试使用它的值。这是undefined behavior.

这将确保 - 在它到达递归调用的底部后，它将 return 值 return 正确编辑，以便后续的父函数得到它。不要忘记 return 只是终止函数的执行并且 return 控制调用函数。

还要注意 - 排序函数通常不 return 任何东西（void return 类型） - 但在这种情况下，经过所有这些工作，你是 returning 就是 0。所以它给我们留下了一个问题 - 你 returning 的值是正确的吗？

您的 maxInd 函数在第一次调用时也会 return 6 - 这是错误的。它不能是您代码中 c as array indexing is 0-based on c. Otherwise you are invoking Undefined Behavior 中长度 6 数组中的有效索引。正确的顺序是 - 首先检查它（index）是否超出范围，如果是，那么在这种情况下 return index 否则通过连续进行寻找它来电。

if(i == len)
    return index;

if (arr[i] > max){
    max = arr[i];
    index = i;
}

只需更正代码 - 给出正确的结果。（从您的代码中删除未定义的行为）（我所说的正确结果是指它对数组进行排序，但您最不关心它）。 Here.

另外正如 Jonathan Leffler 所提到的，您代码中的缩进具有误导性。编译器生成的消息是 [-Werror=misleading-indentation]，您应该相应地对待它。您可以看到正确的缩进如何消除此错误。

递归选择排序在 C 中输出不正确的值

Recursive selection sort outputting incorrect values in C

c

recursion

selection-sort