选择排序的优化反而比原本的更慢了

Question

您给的代码中有一小节是优化选择排序的，思路巧妙，每一轮中找到当前未处理元素的最大值与最小值，但是这种算法测试效果却还没有原本没有优化的好，请问是什么原因，我感觉比原来的应该快近一倍，事实上慢了许多。下面的InsertionSort是您优化过的。

Answer 1

liuyubobobo 2018-07-27 17:41:11

很奇怪，我无法解释。我刚才测试了一下，在我的计算机上，优化后的SelectionSort2稳定的优于不优化的SelectionSort，除了对于第二个测试用例，包含大量重复数据的数组。（jdk1.8.0_131）

对于你的测试结果，我只能猜测和jvm的内部优化有关，甚至调用顺序都会对性能有影响。毕竟java是运行在虚拟机上的，虚拟机的具体实现会对代码效率产生很大影响。比如这个问答：https://coding.imooc.com/learn/questiondetail/30054.html

抱歉没有回答你的问题。

加油！

• 提问者 Anthony_Duan #1

  理论上应该是优化过的应该是更优的应该没错吧

• 提问者 Anthony_Duan #2

  非常感谢！

• liuyubobobo 回复 提问者 Anthony_Duan #3

  理论上是。但是你可以看到，优化的选择排序，其实在第一层循环内使用了更多变量（意味着开辟了更多内存），同时使用了更多条件判断或者对于某些测试数据可能有更多的比较，所以实际情况不好说。这也是算法复杂度理论使用大O的原因。因为具体情况千差万别，太难分析一个算法的具体实现了，而且其实也必要性不大，尤其是在现代计算机体系中。从复杂度的角度，这两个算法都是O(n^2)级别的：）

点开查看后面1条评论