我有一个关于数组上的合并排序如何工作的问题。
我理解“划分”步骤,它将输入数组划分为 1 长度的元素。然而,当谈到“合并”部分(组合步骤)时,我感到困惑。
例如,给定输入 3 5 1 8 2,除法过程将产生 5 个元素:3,5,1,8,2。我只知道合并函数会将它们组合成 3 5, 1 8, 2 ,但是它如何继续组合 3 5 和 1 8 ? “组合”部分是否涉及递归?
当两个递归排序例程返回时,您可以放心地假设它们已经对各自的部分进行了排序。合并步骤组合这两个已排序的子数组。如果输入是3 5 1 8 2
,第一个递归调用对前半部分进行排序并产生3 5
,第二个递归调用对后半部分进行排序并产生1 2 8
.
您询问的合并步骤通过重复选择两个子数组的前两个元素中的最小值并将其添加到结果中,将这两个已排序的一半合并为一个,如本动画所示:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)