• 递归实现插入排序

#include <stdio.h>

void insertion_sort(int arr[], int n)
{
    if (n > 1)
    {
        insertion_sort(arr, n - 1);

        arr[0] = arr[n];
        int i;
        for (i = n - 1; i > 0; i--)
        {
            if (arr[i] > arr[0])
            {
                arr[i + 1] = arr[i];
            }
            else
            {
                break;
            }
        }
        arr[i + 1] = arr[0];
    }
}

int main()
{
    int arr[] = {0, 5, 3, 8, 6, 2, 7}; // 哨兵在 arr[0]，实际元素从 arr[1] 开始
    int n = 6; // 数组中实际待排序的元素个数

    insertion_sort(arr, n);

    for (int i = 1; i <= n; i++) // 输出排序后的数组，从 arr[1] 开始
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

原理：

整个流程的详细讲解：

1. 初始数组：arr[] = { 0, 5, 3, 8, 6, 2, 7 }。

   • 哨兵 arr[0] = 0，实际待排序的元素从 arr[1] 开始：[5, 3, 8, 6, 2, 7]。

2. 第一次递归 (n = 6):

   • 递归调用 insertion_sort(arr, 5) 排序前 5 个元素 [5, 3, 8, 6, 2]。

3. 第二次递归 (n = 5):

   • 递归调用 insertion_sort(arr, 4) 排序前 4 个元素 [5, 3, 8, 6]。

4. 第三次递归 (n = 4):

   • 递归调用 insertion_sort(arr, 3) 排序前 3 个元素 [5, 3, 8]。

5. 第四次递归 (n = 3):

   • 递归调用 insertion_sort(arr, 2) 排序前 2 个元素 [5, 3]。

6. 第五次递归 (n = 2):

   • 递归调用 insertion_sort(arr, 1) 排序前 1 个元素 [5]。此时递归停止，因为 n <= 1。

7. 回溯递归过程：

   • 返回 n = 2，arr[0] = 3，执行插入操作，数组变为 [3, 5]。
   • 返回 n = 3，arr[0] = 8，数组变为 [3, 5, 8]。
   • 返回 n = 4，arr[0] = 6，数组变为 [3, 5, 6, 8]。
   • 返回 n = 5，arr[0] = 2，数组变为 [2, 3, 5, 6, 8]。
   • 返回 n = 6，arr[0] = 7，数组变为 [2, 3, 5, 6, 7, 8]。

8. 输出排序后的数组：

   • 输出从 arr[1] 开始的元素：2 3 5 6 7 8。

完整排序过程：

• 排序前：[0, 5, 3, 8, 6, 2, 7]
• 排序后：[2, 3, 5, 6, 7, 8]

• 递归实现选择排序

#include <stdio.h>

void selection_sort(int arr[], int n)
{
    if (n > 1)
    {
        // 找到从前 n 个元素中最大值的索引
        int max_index = 0; // 假定第一个是最大值
        for (int i = 1; i < n; i++) // 遍历前 n 个元素
        {
            if (arr[i] > arr[max_index])
            {
                max_index = i;
            }
        }

        // 将最大值与最后一个元素交换
        int temp = arr[n - 1];
        arr[n - 1] = arr[max_index];
        arr[max_index] = temp;

        // 递归调用，排序前 n-1 个元素
        selection_sort(arr, n - 1);
    }
}

int main()
{
    int arr[] = { 64, 25, 12, 22, 11 }; // 输入数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组长度

    selection_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) // 输出排序后的数组
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

• 递归实现冒泡排序

#include <stdio.h>

void bubble_sort(int arr[], int n)
{
    // 基本情况：如果数组大小为 1 或 0，直接返回
    if (n <= 1)
        return;

    // 一次遍历，将当前范围内的最大值移动到末尾
    for (int i = 0; i < n - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            // 交换相邻元素
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }

    // 递归调用，对前 n-1 个元素排序
    bubble_sort(arr, n - 1);
}

int main()
{
    int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
    int n = sizeof(arr) / sizeof(arr[0]);

    bubble_sort(arr, n);

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

    return 0;
}

递归实现折半查找

#include <stdio.h>

// 函数声明
int binarySearch(int arr[], int target, int left, int right);

int main() {
    int arr[] = {2, 3, 4, 10, 40}; // 示例数组，必须是有序的
    int n = sizeof(arr) / sizeof(arr[0]); // 数组元素个数
    int target = 10; // 要查找的目标值
    int result = binarySearch(arr, target, 0, n - 1);

    if(result != -1) {
        printf("元素 %d 位于数组索引 %d.\n", target, result);
    } else {
        printf("元素 %d 未找到。\n", target);
    }

    return 0;
}

// 折半查找的递归函数
int binarySearch(int arr[], int target, int left, int right) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        // 检查是否找到目标值
        if (arr[mid] == target) {
            return mid;
        }

        // 如果目标值小于中间元素，则在左半部分查找
        if (arr[mid] > target) {
            return binarySearch(arr, target, left, mid - 1);
        }

        // 如果目标值大于中间元素，则在右半部分查找
        return binarySearch(arr, target, mid + 1, right);
    }

    // 如果元素未找到
    return -1;
}