c - 合并排序算法

Question

首先让我说这是硬件，所以我正在寻找更多的建议而不是答案。我要编写一个程序来读取输入序列，然后生成一个链接数组，按升序给出值。

输入文件的第一行是序列的长度(n)，其余n行每行都是一个非负整数。这 输出的第一行表示最小输入值的下标。剩下的每一行输出都是一个三元组 由下标以及相应的输入序列和链接值组成。

(递归排序开始前不初始化链接值，当每个链接的序列值放在递归树底部的单个元素列表中时，每个链接将被初始化为-1)

输出看起来像这样:

0  3  5
1  5  2
2  6  3
3  7  -1
4  0  6
5  4  1
6  1  7
7  2  0

其中(我认为)最后一列是下标，中心是未排序的数组，最后一列是链接值。我已经有了 mergeSort 的代码并了解它是如何工作的我只是感到困惑以及链接是如何放置的。

Answer 1

我使用结构 vector 来保存每行的三个值。

主要步骤是:

• 初始化索引并从输入中读取值
• 按值对 vector 排序
• 确定链接
• 按索引对 vector 排序(返回)

这是代码的草图:

struct Element {
    int index;
    int value;
    int nextIndex; // link
}

Element V[N + 1];
int StartIndex;

V[i].index = i;
V[i].value = read_from_input;

sort(V); // by value

startIndex = V[0].index;
V[i].nextIndex = V[i + 1].index;
V[N].nextIndex = -1;

sort(V); // by index