• 递归实现插入排序

#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;
}