###插入排序 精髓就是首先将第一个元素视为有序子数组x[0...0]，然后插入x[1]...x[n-1].思想很简单，代码也很简单，简单的代码有没有优化的空间呢？编程珠玑中提供了几个优化后的方案，效率提高了70%之多 ### 简单的实现（sort1） ~~~ void insertSort(int *array, size_t size){ for(size_t i = 1; i < size; i++){ for(int j = i; j > 0 && array[j - 1] > array[j]; j--){ swap(array[j - 1], array[j]); } } } ~~~ 优化思路：内循环的swap函数可能不如内联函数快些，所以第一步优化将该swap函数展开，据作者说，展开后效率提高了60%。 ### 优化代码（sort2） ~~~ void insertSort(int *array, size_t size){ for(size_t i = 1; i < size; i++){ for(int j = i; j > 0 && array[j - 1] > array[j]; j--){ int t = array[j]; array[j] = array[j - 1]; array[j - 1] = t; } } } ~~~ 优化思路：由于内循环中总是给变量t赋同样的值（x[i]的初始值），所以内循环关于t的两条赋值语句移出循环，据说这么做的效率又提高了15%。 ### 优化代码（sort3） ~~~ void insertSort(int *array, size_t size){ for(size_t i = 1; i < size; i++){ int j = i; int t = array[j]; for(; j > 0 && array[j - 1] > array[j]; j--){ array[j] = array[j - 1]; } array[j] = t; } } ~~~ 书中给出了三种排序的运行时间：  插入排序的效率总是O(n2)，效率差在比较的次数以及交换的频率，如果交换的频率减少的话就可以大大提高插入排序的效率，这也是为什么元素基本有序时插入排序效率高的原因。 ### 总结归纳 代码调优以及性能优化都可能带来一系列的副作用，比如程序的正确性，可读性，可维护性等。是否需要调优要看问题性质，调优既是华而不实的“花活”，也是一把利刃，区别就在于使用的场合。 **转载请注明出处**：[http://blog.csdn.net/utimes/article/details/8761722](http://blog.csdn.net/utimes/article/details/8761722)