2024年陕西科技大学数据结构程序填空题+预测

• 递归实现插入排序

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