我正在观看关于归并排序的 Coursera 普林斯顿算法讲座,我理解所有分析,除了归并最多 6 n log n 数组访问。
为什么是 6?
最佳答案
为了获得 6 个数组访问,一个有点低效的合并过程:
read - read an element from even run for compare
read - read an element from odd run for compare
- compare
read - read the lower element again for copy
write - write the lower element to the output array for copy
... - after merge copy back
read - read element from output array to copy back
write - write element back to original array to copy back
正常情况是每个移动的元素一次读取和一次写入,但考虑到元素太大而无法放入变量的情况,例如字符串,因此在比较之后,必须读取要移动的字符串再次。
通常可以避免复制回操作,这取决于合并排序的编码方式。
关于algorithm - 为什么合并排序最多有 6 n log n 数组访问?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33265686/