7-1 直接插入排序 分数 20 作者 黄龙军 单位 绍兴文理学院 给定一个整数序列，请按非递减序输出采用直接插入排序的各趟排序后的结果。 输入格式: 测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。 输出格式: 对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。

这是一道关于排序算法的题目，要求实现直接插入排序，并输出每趟排序后的结果。下面是示例代码：

while True:
    try:
        n = int(input())
        nums = list(map(int, input().split()))
        # 直接插入排序
        for i in range(1, n):
            # 将 nums[i] 插入到前面已经排序好的序列中
            for j in range(i, 0, -1):
                if nums[j] < nums[j-1]:
                    nums[j], nums[j-1] = nums[j-1], nums[j]
            # 输出该趟排序后的结果
            print(' '.join(map(str, nums)))
    except:
        break

这段代码中，我们先读入测试数据的个数 n 和 n 个整数。然后，我们使用两个 for 循环实现直接插入排序，其中外层循环表示进行了几趟排序，内层循环表示对前面已经排序好的序列进行插入操作。每进行一趟排序，就输出该趟排序后的结果。最后，我们使用 try-except 语句来处理多组测试数据的情况。

相关问题

7-1 入度与出度分数 10作者 黄龙军单位 绍兴文理学院求有向图g中各顶点的入度与出

有向图中，每个顶点有两个相关的度数，即入度和出度。

入度表示指向该顶点的边的数量，而出度表示从该顶点出发的边的数量。

假设有向图g有n个顶点，则每个顶点的入度与出度可以用两个n维向量来表示。

设向量D表示每个顶点的入度，向量O表示每个顶点的出度，则有：

D = [d1, d2, ..., dn]，O = [o1, o2, ..., on]

其中，di表示第i个顶点的入度，oi表示第i个顶点的出度。

通过遍历每个顶点，可以计算出它们的入度和出度。

具体计算方法如下：

1. 初始化D和O为长度为n的全0向量。
2. 遍历有向图g的每个边，若边的起点是i，终点是j，则将D的第j个元素增加1（即dj = dj + 1），将O的第i个元素增加1（即oi = oi + 1）。
3. 遍历完成后，得到了每个顶点的入度和出度。

举个例子，假设有向图g有4个顶点，边的表示如下：

1 -> 2
1 -> 3
2 -> 3
3 -> 4

则有：

D = [0, 2, 2, 1]
O = [0, 1, 2, 1]

其中，顶点1的入度为0，出度为2；顶点2的入度为2，出度为1；顶点3的入度为2，出度为2；顶点4的入度为1，出度为1。

通过计算每个顶点的入度和出度，可以帮助我们更好地理解有向图的结构，并在分析图的特性和性质时提供参考依据。

7-2 二路归并排序 分数 15 作者 黄龙军 单位 绍兴文理学院 给定一个整数序列，请按非递减序输出采用二路归并排序（递归法）的各趟排序后的结果（每完成一次归并操作就输出归并后的结果）。 输入格式: 测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。 输出格式: 对于每组测试，输出若干行，每行是一趟排序后的结果，每行的每两个数据之间留一个空格。 输入样例: 6 73 12 27 98 81 64 输出样例: 12 73 27 98 81 64 12 27 73 98 81 64 12 27 73 81 98 64 12 27 73 64 81 98 12 27 64 73 81 98

以下是该问题的一个可能解法：

#include <iostream>
using namespace std;

const int N = 110;

int n;
int a[N], b[N];

void merge_sort(int l, int r)
{
    if (l == r) return;
    int mid = (l + r) / 2;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int i = 0; i < k; i++) a[l + i] = b[i];
    for (int i = l; i <= r; i++) cout << a[i] << " ";
    cout << endl;
}

int main()
{
    while (cin >> n)
    {
        for (int i = 0; i < n; i++) cin >> a[i];
        merge_sort(0, n - 1);
    }
    return 0;
}

该算法的时间复杂度为 $O(n\log n)$，其中 $n$ 是序列的长度。首先将序列分成两部分，然后对每部分递归地进行排序，最后将两部分合并成一个有序序列。每次合并时，需要比较两部分的元素大小，并按顺序合并。在合并的过程中，需要辅助数组 $b$ 来存储合并的结果。每完成一次归并操作，就输出归并后的结果。