选择排序性能分析疑问

Question

老师，我在分析选择排序对随机数组和近乎有序数组排序的性能差异时，我认为在数组长度一致的条件下，选择排序对近乎有序的数组排序时间应该更短，原因是在查找 [i,数组长度)这个区间内的最小值的时候，找到的最小值，多数时候还是i本身，就不用进行交换了， 但是在实际测试的时候，发现两种情况下，选择排序的用时差别不大，甚至对近乎有序数组的排序时间更长一点，希望老师有时间的时候看看我的分析对不对。

以下是js版本代码的测试结果，其余排序的结果是正常的，只有选择排序不在我的预料内。
麻烦老师了，感谢！！

Answer 1

liuyubobobo 2020-09-10 05:59:08

其实对于我们写的代码，二者的交换次数是没有差距的，都是会交换 n 次。只不过在完全有序的数组中，每次都是自己和自己交换而已。

如果添加一个 if(minIndex != i) 才做交换，虽然理论上对完全有序的数组少了交换，但其实每次多做了一个 if 判断。

所以，对于真正有序的数组，真正减少的性能开销在于少运行了内层 for 循环 if 成功以后的 minIndex = j 这一句话。但是这句话本身的影响很少。那个 if 判断顶好几个这一句话。因为 arr[j] < arr[minIndex] 背后除了比较运算还有从 arr 中访问数据。

不过对于比较大的数据量，应该也能测出差距。我在我的环境中，Java 语言，10 万数据，结果如下：有序数组快 500ms。

不过这个性能差距也应该和语言相关。整体，我是不很建议使用脚本语言做算法实现的性能评测的，因为脚本语言的代码性能过度依赖解释器的执行优化，很多时候，代码逻辑层面理论上的“优化”，尤其是常数级的优化，反而会让代码运行更慢。

继续加油！：）

• 提问者 慕粉4283821 #1

  非常感谢老师的分析，让我对性能分析有了更深的理解，以后也学会从每行代码去分析~