无法理解合并排序算法中实际创建了多少个数组
我一直在研究合并排序算法，但我无法断定实际创建了多少数组作为该算法的一部分。某些文献指出，整个原始数组被复制到一个排序的新数组中。但这意味着只创建了2个数组。
据我所知，合并排序算法有两个主要步骤。分裂和合并。我想，如果你给合并排序一个由100个插槽组成的数组，它实际上创建了新的数组，当它从100 > 50/50 > 25/25 > 12/13 > 6/5 > 3/3 > 1/1的中间分开时，它在内存中有12或13个数组。最后，它将所有这些复制到1>2>3或4>6> 12 > 25 > 50 > 100的新数组中。
这是另外8个数组(粗略地说)。
但在教科书里我读到了这样的东西：
您可能想知道所有这些子数组在内存中的位置。在该算法中，创建与原始数组大小相同的工作区数组。子数组存储在工作区数组的各个部分中。这意味着原始数组中的子数组被复制到工作区数组中的适当位置。每次合并后，工作区数组将被复制回原始数组中。
- Java中的数据结构和算法
回答 3
Stack Overflow用户
发布于 2016-03-22 17:23:53
考虑典型合并排序实现的两个最后阶段。我们需要两个数组-主数组和辅助数组，并将子数组从aux数组合并到主数组。
在某些合并阶段之前(|表示每个数组段的开始(起始索引))--我们将A子数组与B子数组合并以填充目标数组的前半部分，并将C子数组与D子数组合并以填充目标数组的后半部分：
Auxiliary array: |AAAA|BBBB|CCCC|DDDD
Main array: ..................合并后(我使用任意排序)
Auxiliary array: ...............
Main array: ABBABBAADCDDCCDC复制后，最后合并之前
Auxiliary array: |ABBABBAA|DCDDCCDC
Main array: ................Stack Overflow用户
发布于 2016-03-22 16:55:15
即使您“拆分”您的数组，您也不必创建2个新数组。您总是有相同数目的插槽(这里有100个，即使是50*2或25*4.)
您只需在数组中正确的位置移动数据(在第一次拆分之后，50个第一个插槽是第一个数组，最后50个插槽是第二个数组)。
您不需要存储数组，只需要索引它们在大数组中的起始位置。
Stack Overflow用户
发布于 2016-03-22 20:15:23
教科书是指合并的合理有效的实现，其中工作空间数组的一次分配与原始数组的大小相同。在此之后，所有要合并的子数组都是通过索引(或指针)访问的工作区数组或原始数组的一部分。
自顶向下的合并排序使用递归生成表示子数组的一对索引的动态堆栈。自下而上的合并排序跳过递归，并使用迭代生成索引，从子数组大小为1开始。
https://stackoverflow.com/questions/36160195
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号