###插入排序 精髓就是首先將第一個元素視為有序子數組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)