没优化时插排就优于选排

Question

和老师一样的写法，但多次测验都是插入排序优于选择排序，这是什么原因呢？是Clion自动优化了吗？

Answer 1

liuyubobobo 2018-03-06 12:08:39

有可能。毕竟插入排序是可能提前终止内层循环的。

同样的程序，在不同的电脑，用不同的编译器，不同的优化参数（-o1, -o2, -o3, -o4），在不同的操作系统上，对性能都会产生影响。即使上述条件都相同，每次运行，性能也都可能有甚至是不小差别，尤其是当数据量较小的时候。因为每次运行，操作系统的工作环境和任务调度也是不同的。如果希望获得更加准确的性能结果，一方面需要加大数据规模，另一方面需要多次测试取平均值，结果才能相对比较好的说明算法的性能。

我在这个课程的补充代码中，使用这样的思路，对Shell Sort, Merge Sort 和 Quick Sort进行了性能比较。可以看到，我是用的比较方式是，对100万级别的数据，每个算法运行100次，取性能平均值，作为最终的性能结果。代码参见这里：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-03-ShellSort-MergeSort-and-QuickSort-Comparision/main.cpp

不过，其实我不建议大家花费太多的时间用来比较同样的复杂度级别的算法性能。有一个感性的认识就好了。虽然C++相对而言可以比较好的反应程序指令的执行效率，但是不同的C++编译器仍然有自己的优化，再加上操作系统在内存调度上的优化等影响。所以两个同样时间复杂度的算法，细微的性能差异，其实意义并不大。毕竟，学习算法的真正意义，是通过实现更优时间复杂度的算法，让不可能化为可能：）

但是，对于选择排序和插入排序，一定要掌握的是：

1）选择排序每一对元素之间一定会进行一次比较，所以他是比较次数最多的排序算法；但是选择排序只需要交换n-1次元素，是交换次数最少的排序算法

2）插入排序在有序的情况下，会“进化”成为O(n)的算法。这位后续使用插入排序优化高级排序算法留下了基础：）

• 提问者 一轩明月 #1

  非常感谢！