替代插入排序+复制小数组时必须排序*和*复制
替代插入排序+复制小数组时必须排序*和*复制
提问于 2013-09-12 12:24:47
考虑两个数组，A和B，两者的长度都是N，N相当小。我想对A中的元素进行排序，并将排序后的元素存储在B中。
在A上执行就地插入排序，然后将排序后的值大容量复制到B中是非常简单的，但是，这不能充分利用以下两点：
- 有N号的划痕空间可供使用和
- 排序后的值最终必须在B而不是A中结束。
有人能提出不同的方法(可能是修改的插入排序吗？)这将利用其中的一个(或两者)，并最终超过简单的解决方案插入排序+复制？
回答 1
Stack Overflow用户
发布于 2016-12-09 03:29:36
很多年后来的，但如果有人有机会，这是我的两分钱。使用插入排序与诸如合并排序之类的快速离开位置排序的组合可能会提供一些最小的改进。
- 将数组拆分为季度，并使用插入排序进行排序。
- 将第一和第二季度合并到划痕空间，第三和第四季度相同
- 从零开始将前半部分和下半部分合并到目标数组中。
同样，这可能提供了最小的实际改进，而且可能是过早优化的情况。您最好对您的应用程序进行基准测试，看看您是否真的需要改进算法的这一部分，或者您的时间是否更好地用于优化其他内容。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18764217
复制相关文章
相似问题
腾讯云开发者
