递归算法实现选择排序（YOJ2.0中的题）

一遍过！

没有草稿！没有任何错误！

太爽了！

因为必须是倒序输出，所以只能用递归，比起之前做的一题，这一题要求是比较严格的

而且最后正确的数列顺序是在改变步骤之后输出，而改变步骤必须伴随着改变后的数组输出

所以你得先正确选择排序一遍，得到排序后的数组，用新数组记录下来，旧数组随着改变步骤的输出而不断变回最开始的那个数组

最后输出步骤数和新数组

代码如下：

#include<stdio.h>
void function(int location);
int num[101];
int num_last[101];
int n;
int m;//交换次数

int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)//从1开始记录
        scanf("%d", &num[i]);
    function(1);
    printf("Total steps:%d\n", m);
    printf("Right order:");
    for(int i = 1; i <= n; i++)
    {
        printf("%d", num_last[i]);
        if(i != n)
            putchar(' ');
    }
    
    return 0;
}
void function(int location)
{
    int min = num[location], min_loc = location;
    for(int i = location + 1; i <= n; i++)
        if(min > num[i])
        {
            min = num[i];
            min_loc = i;
        }
    if(min_loc != location)
    {
        m += 1;
        num[min_loc] = num[location];
        num[location] = min;
    }

    //递归
    if(location != n - 1)
        function(location + 1);
    else
        for(int i = 1; i <= n; i++)
            num_last[i] = num[i]; 

    //输出
    if(min_loc != location)
    {
        printf("%d<->%d:", location, min_loc);
        for(int i = 1; i <= n; i++)
            printf("%d%c", num[i], (i == n) ? '\n' :' ');
        num[location] = num[min_loc];
        num[min_loc] = min;
    }

    return;
}