选择排序处理有序数据的时候似乎也有性能提升
我电脑上关于选择排序和插入排序的性能测试结果如下：
random array: InsertionSort sort with n = 1000, cost: 0.004026 SelectionSort sort with n = 1000, cost: 0.004982 ordered array: InsertionSort sort with n = 1000, cost: 0.000031 SelectionSort sort with n = 1000, cost: 0.003383 random array: InsertionSort sort with n = 10000, cost: 0.128251 SelectionSort sort with n = 10000, cost: 0.112935 ordered array: InsertionSort sort with n = 10000, cost: 0.000628 SelectionSort sort with n = 10000, cost: 0.062827 random array: InsertionSort sort with n = 100000, cost: 6.143175 SelectionSort sort with n = 100000, cost: 12.512976 ordered array: InsertionSort sort with n = 100000, cost: 0.000382 SelectionSort sort with n = 100000, cost: 4.129156
可以看到在10万的数据规模下，选择排序针对有序数组用时4.12s，相对于其处理随机数组在常数级别上也有很大的优化。但是根据选择排序的原理其实不应该在处理有序数组时有这样明显的提升，对这个问题感到疑惑。。
正在回答 回答被采纳积分+1
这种性能的变化来自于：
1）体系结构中优化，比如 CPU 的缓存优化；
2）JVM （包括其他语言的一些编译器）层面的优化，会使得一些看似等同的操作，但实际上从执行底层看是不等同的。比如 swap(a, b)。a 和 b 是否是一个位置，是有很大的差别的。而现代编译器都是可以捕捉到这一差别的。
如果 a 和 b 是一个位置，就可以什么事情都不做；但如果 a 和 b 不一样，则需要先确定 a 和 b 的地址，再交换。无论是逻辑上层（三步交换），还是硬件执行的底层（内存寻址），都有更多的开销。虽然从“高级语言”的层面看，是同样的一个 swap。
3）当代计算机由于普遍是多核环境，大多数编译器也对此有优化，比如这个问题：https://class.imooc.com/course/qadetail/336800
但不管怎样，所有的这些优化都不是“算法层面”考虑的问题。如果对这类“优化”感兴趣，应该去学习类似这样的内容：https://t.zsxq.com/13HqNFsCy
==========
值得一提的是，你可以看见，在你的最后一个测试用例中，插入排序的时间是：0.0003 秒，而选择排序的时间是 4 秒，就算 4 秒比 12 秒快很多，但是面对 0.0003 秒，还是被完全碾压。不管你怎么优化你当前的代码，都很难达到 0.0003 秒的水平。（或许将来以后量子计算可以？）
为什么？这就是复杂度的威力。这就是 O(n) 和 O(n^2) 之间的绝对差距。这种差距，是学习算法要关注的重点。再一次，不是说同复杂度级别的优化不重要，而是这样的优化不是算法领域关注的重点，算法领域关注的是复杂度级别的提升。复杂度级别的提升，是后续我们在各个平台上如何“最优地”实现这个算法的基础。
也可以参考一下这个问题：https://class.imooc.com/course/qadetail/343147
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星