c++ - 从递归向后选择排序函数调用 max 和 swap 函数

Question

家庭作业:我需要编写一个递归向后选择排序函数，不使用循环，调用提供的 swap 函数和 find_Max 函数(这里称为 max)有不同的参数。

要驱动 swap，我需要 max 值的索引；我不知道如何得到它。不幸的是，我不允许将任何参数更改为 swap、Max 或 back_rec_sort。第一个功能是问题；另外两个必须被调用。此外，向后排序意味着找到最大值，将其交换到位置 n-1，然后向 0 索引努力。

//Updated version calling linear search from back_rec_sort as hw question 
does not restrict that.  

void rec_ssort(int arr[], int n)
{
    int last = n -1;

    if (last >= 0)
    {
        int Max = max(arr, 0, last);
        //int index=binarySearch(arr, 0, last, Max);
        int index = search(arr, last, Max);
        swap(arr, index, last);
        rec_ssort(arr, n - 1);
    }
    else
        return;
}

// Linearly search x in arr[].  If x is present then return its 
// location,  otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

int max(int arr[], int start, int end)
{
    //Base case when there is only 1 element left
    if (start == end)
    {
        return arr[start];
    }

    //Compute middle element position  
    int m = (start + end) / 2;

    //Calling the same function with reduced size  
    int left_max = max(arr, start, m);
    int right_max = max(arr, m + 1, end);

    //Combining solutions  
    if (left_max > right_max)
    {
        return left_max;
    }
    else
    {
        return right_max;
    }
}

void swap(int arr[], int i, int j)
{
    int temp;
    temp =arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Answer 1

写下来这样我们就可以存档问题......

(1) 编写一个线性搜索函数，接受数组和一个值，然后返回该值在数组中的索引。

int search(int arr[], int n, int target)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] == target)
            return i;
    }
    return -1;   // if not found
}

(2)-1失败返回导致数组访问越界——这是原代码和查找函数的协调问题。删除该行会返回 NULL，这会导致他需要的功能。