插入排序

先說下插入排序實作過程：

     對要排序的數組，逐個進行處理，與前面的子序列進行比較，讓它插入到合适的位置。

時間複雜度：

      某一個子產品的函數f()的增長率越小，整個程式執行時間增長率就越小，注意這個裡面是指的是函數的增長率就是所說的時間複雜度。它是衡量算法好壞的标準之一，時間複雜度越小，算法的效率越高。 現在的電腦都可以滿足小程式所需要的記憶體，如果遇到比較大的資料群，換台更大點的電腦不實際，優化算法才是最合适的選擇。

插入排序的時間複雜度是Ο（n^2）：

        這個很早就知道但是它是怎們來的納？今天花了點時間，琢磨了一下，不僅僅是翻到了《資料結構與算法》還翻到了《高等數學》，下面是我個人的了解。

插入排序當中，主要通過兩個函數f()确定時間複雜度：

  1）要插入進去的關鍵字與已知子序列之間的比較次數；

  2）比較完成之後的序列中移動次數；

          嗯，可以開始分析了；先分為兩種情形：

 1）最幸運：所要排序的數組恰好已經是從小到大的排列起來的，比如（1，2，3，5，6，7，8、、）看看上面兩個函數結果，比較次數是（n-1），要移動的次數是0；

 2) 最倒黴： 所要排序的數組整個都是逆序的，也就是說是從大到小排列的，比如（7，6，4，2，1、、、），推出比較次數的函數表達式用到了等差數列前n項和的公式，應該是（n+2）（n-1）/2，那麼後面的移動次數根據同樣的原理是（n+4）（n-1）/2；

     ok，上面過程當中的最幸運和最倒黴分别對應的是定義時間複雜度時的下限和上限，每次所要排序的資料都是随機的，排序當中的資料出現各種排序方式的機率是相同的，取上面兩種情形最小值和最大值的平均，應該是n^2/4,最後對這個表達式求極限，就是插入排序的時間複雜度了。

     貼段自己寫的插入排序：

  有點自己的感想：

    java已經提供了很好的排序算法的類，隻要引用裡面的方法就可以了，還有必要在學習排序算法，分析其中的過程嗎？

    這樣程式員就會慢慢和搞數學的畫上等号，我自己覺得，在這個方面應該就是外面的各種教育訓練機構所不能做到的地方，也就是這個地方是大學生比其他教育訓練機構具有的優勢，可以分析程式背後純數學的簡單問題。

如果，您認為閱讀這篇部落格讓您有些收獲，不妨點選一下右下角的【推薦】 

如果，您希望更容易地發現我的新部落格，不妨點選一下左下角的【關注我】 

如果，您對我的部落格内容感興趣，請繼續關注我的後續部落格，我是【orson】 

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段 聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。 

轉載：http://www.cnblogs.com/java-class/archive/2012/12/26/2834717.html