题目

给定k个排好序的序列s1,s2,…,sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。

1
2
测试用例：5 12 11 2
输出： 52

算法

1
2
3
4
5
6
7
8
9
10
11
//输入：长度为n的序列a;
//输出：最少总比较次数
getMin(A, n)
{
     int min ← 0;
     for i ← 0 to n - 1 do
        qsort(a + i, n - i, sizeof(int), &cmp1); //升序排序
        a[i + 1] ← a[i + 1] + a[i];
        min ← min + a[i + 1] - 1;
     return min;
}

时间复杂度分析

基础运算为函数中的运算：
赋值（2）+（qsort排序（nlogn））n + （for内赋值（2））n + 返回值（1）=$3+2n+n^2logn$
所以时间复杂度为$O(n^2logn)$

全部代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

//升序
int cmp1(const void* a, const void* b)
{
    return *(int*)a - *(int*)b; 
}

//降序
int cmp2(const void* a, const void* b)
{
    return *(int*)b - *(int*)a;
}

//最优情况
int getMin(int *a, int n)
{
    int min = 0;                    //初始化min的值
    for (int i = 0; i < n - 1; i++) //循环n次
    {
        qsort(a + i, n - i, sizeof(int), &cmp1); //由低到高，升序排序
        // printf("%d+%d=%d\n", a[i + 1],a[i],(a[i+1]+a[i]));
        a[i + 1] += a[i];                        //更改数据
        // printf("min:%d+%d-1=%d\n",min,a[i+1],(min+a[i+1]-1));
        min += a[i + 1] - 1;
    }
    printf("最优情况min=%d\n", min);
    return min;
}

//最差情况
int getMax(int *b, int n)
{
    int max = 0;
    for (int i = 0; i < n - 1; i++)
    {
        qsort(b + i, n - 1, sizeof(int), &cmp2); //降序
        // printf("%d+%d=%d\n", b[i + 1],b[i],(b[i+1]+b[i]));
        b[i + 1] += b[i];
        // printf("max:%d+%d-1=%d\n",max,b[i+1],(max+b[i+1]-1));
        max += b[i + 1] - 1;
    }
    printf("最差情况max=%d\n", max);
    return max;
}

int main()
{
    int a[100], b[100];
    int n;

    //读取数据
    FILE *f1 = fopen("E:/这是E盘的桌面/program/C_Document/202210031137/input.txt", "r");
    if (f1 == NULL)
    {
        printf("文件打开失败");
        return 0;
    }
    fscanf(f1, "%d", &n);
    printf("要合并的序列为：");
    for (int i = 0; i < n; i++)
    {
        fscanf(f1, "%d", &a[i]);
        printf("%3d", a[i]);
        b[i] = a[i];
    }
    printf("\n");
    fclose(f1);

    //输出数据
    int min = getMin(a, n);
    int max = getMax(b, n);
    FILE *f2 = fopen("E:/这是E盘的桌面/program/C_Document/202210031137/output.txt", "w");
    fprintf(f2, "%3d,%3d", min, max);
    fclose(f2);
    return 0;
}