对存储在不同机器上的数字进行排序

引言

在这个问题中，我们有若干台机器。每台机器上都存储了一些已排序的数字。但每台机器上的数字数量没有固定。从每台机器输出的数字是按降序排列的。

让我们通过一个例子来看一下。

方法一

示例

机器 M1 包含 3 个数字：{30, 40, 50}

机器 M2 包含 2 个数字：{35, 45}

机器 M3 包含 5 个数字：{10, 60, 70, 80, 100}

输出：{10, 30, 35, 40, 45, 50, 60, 70, 80, 100}

我们可以将每条数字流表示为链表的形式。借助最小堆，我们可以按排序顺序打印所有数字。借助以下步骤，**我们可以执行该操作。**

• 首先，我们将链表的头指针存储在一个最小堆中。最小堆的大小为 N。这里，N 代表机器的数量。
• 然后，我们必须提取最小堆中的最小元素。然后，我们需要通过用链表中的下一个数字替换最小堆的头部，或者用最小堆中的最后一个数字替换最小堆的头部，然后将堆的大小减 1 来更新最小堆。

让我们通过编程语言来解决上述问题。

C++ 中的实现

输出

说明

在上面的代码中，我们用 C++ 语言实现了上述问题的方法。在这里，我们首先创建了一个链表，然后向该链表中添加了一些元素。之后，我们实现了一些方法，并借助这些方法解决了上述问题。

方法 2

在这个方法中，我们将合并不同机器上的不同排序列表。在这里，我们需要创建一个 mergeList() 函数，它接受链表向量；然后，它借助最小堆将它们合并成一个单一的排序链表。然后，我们需要创建另一个 externalSort() 函数，它将链表转换为向量。然后，我们需要调用 mergeList() 来排序列表。然后，我们需要打印列表。

让我们通过编程语言来看看这个方法。

C++ 中的实现

代码

输出

说明

在上面的代码中，我们根据上述方法中讨论的内容，在 C++ 中创建了一些函数来操作数组。成功排序数组后，我们打印了它。