c语音设计并实现一个递归函数的直接插入排序算法

在C语言中，你可以通过递归的方式来实现直接插入排序算法，不过通常我们不会推荐在大规模数据排序时使用递归，因为递归会消耗更多的栈空间。下面是一个简单的直接插入排序递归版本的示例：

#include <stdio.h>

// 递归版本的直接插入排序函数
void recursive_insertion_sort(int arr[], int n) {
    // 基线条件：如果数组只有一个元素或为空，直接返回
    if (n <= 1)
        return;

    // 选择最后一个元素作为基准值
    int key = arr[n - 1];

    // 将基准值插入到已排序部分的正确位置
    // 递归地对剩余元素进行排序
    recursive_insertion_sort(arr, n - 1);

    // 插入操作
    int j;
    for (j = n - 2; j >= 0 && arr[j] > key; j--)
        arr[j + 1] = arr[j];
    arr[j + 1] = key;
}

// 主函数测试
int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    recursive_insertion_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

这个程序首先检查数组是否只有一个元素或为空，如果是则停止递归。然后从最后一个元素开始，将它与前面已排序的部分逐个比较，并将它插入到合适的位置。