我来提供第三个归并排序的优化办法

Question

经过测试，这种优化方式，当处理的数据越大，优化效果就越明显。
当然看图就知道了，因为减少2Nlong(N)-2次的临时数组内存空间的开辟和撤销操作。

Answer 1

liuyubobobo 2020-03-27 00:51:28

感谢分享：）

如果我没有理解错，你的方式是整体只开一次临时数组。是的，这是归并排序的一个重要的优化，我在这个课程的补充代码中提供了这个思路的参考代码，可以参考这里：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-01-MergeSort-Create-aux-Array-Out-of-Merge/MergeSort2.h

继续加油！：）

• 提问者 潇潇雨歇兮我材天生 #1

  哈哈，感谢回复，可能是我没仔细查看学习资料，原来老师早已经洞察一切。
  还有个小问题，思路比较新颖，我结合老师您的代码来问一下哈~
  我看到的第4个优化办法，优化结果适得其反、使得性能下降了，具体的优化是 避开 for( int i = l ; i <= r; i ++ )
          aux[i] = arr[i];数组拷贝的开销，采用在每一轮归并时都变更数组实参（即aux替代arr）的方式来等效，即只修改一行代码：
   __merge2(arr, aux, l, mid, r);改为
   __merge2(aux, arr, l, mid, r);
  经我测试和探索，目前还不知道为何优化会失败。不过感觉思路是可行的。每两相邻轮次的归并处理的是不同的数组对象，一轮一换。
  博客出处：https://blog.csdn.net/tinyDolphin/article/details/78457343

• 提问者 潇潇雨歇兮我材天生 #2

  非常感谢！

Answer 2

提问者 潇潇雨歇兮我材天生 2020-03-26 20:46:48

殊途同归，举一反三。

Answer 3

提问者 潇潇雨歇兮我材天生 2020-03-26 20:45:30

将临时数组作为指针传递即可，对了，如此设计以后，还可以不用再去 索引定位执行-left的操作，看来优化的次数远比我说的还要多的多。

各位同学和老师如何看？虽然这并不能引起数量级的改变，但是减少一半多以上时间是轻易地了。