关于合并排序代码中的合并步骤的混淆 [英] Confusion about the combine step in Merge Sort Code

问题描述

我有一个关于数组合并排序如何工作的问题。 我理解‘Divide’步骤，它将一个输入数组分成1个长度的元素。然而，当谈到‘合并’部分(合并步骤)时，我就糊涂了。 例如，给定输入3 5 1 8 2，除法过程将产生5个元素：3，5，1，8，2。我只了解合并函数会将它们组合为3 5，1 8，2，但它如何继续组合3 5和1 8？‘Combine’部分中是否涉及递归？

推荐答案

当两个递归排序例程返回时，您可以安全地假定它们已经对其各部分进行了排序。合并步骤组合这两个排序的子数组。如果输入为3 5 1 8 2，则第一个递归调用对前半部分进行排序并生成3 5，第二个递归调用对后半部分进行排序并生成1 2 8。

您询问的合并步骤，通过重复选择两个子数组的前两个元素中的最小值并将其添加到结果中，将这两个排序的一半合并为一个，如下面的动画所示：

这篇关于关于合并排序代码中的合并步骤的混淆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！