插入排序法：所謂插入排序法乃是将一個數目插入該占據的位置。
假設我們輸入的是 “53，27，36，15，69, 42” 我們從第二個數字開始，這個數字是27，我們的任務隻要看看27有沒有正确的位置，我們的做法是和這個數字左邊的數字來比，是以我們比較27和53，27比53小，是以我們就交換27和53，原來的排列就變成了“27, 53, 36, 15, 69, 42 ”
接下來，我們看第3個數字有沒有在正确的位置。這個數字是36，它的左邊數字是53，36比53小，是以我們将36和53交換，排列變成了 “27,36, 53,
15, 69, 42 "我們必須繼續看36有沒有在正确的位置，36的左邊是27，27比36小，36就維持不動了,這時候排序還是“27, 36, 53,
15, 69, 42 "。
再來看第四個數字，這個數字是15，我們将15和它左邊的數字相比，都比15大，是以就将15一路往左移動，這時候排序變成了 “15, 27, 36, 53,
69, 42 ”。
再來看第五個數字，這個數字是69，我們将69和它左邊的數字相比，都比69小，是以就69維持不動了，這時候排序變成了
“15, 27, 36, 53,
69, 42 ”
最後，我們檢查第六個數字，這個數字是42，42必須往左移，一直移到42的左邊是36為止，是以我們的排列就變成了 “15, 27, 36, 42 ,53,
69”排序是以完成了。
ps:讀者也可以自己打開下面的連結，自己設定要排序的數組，進行排序演練
所謂插入排序法，就是檢查第i個數字，如果在它的左邊的數字比它大，進行交換，這個動作一直繼續下去，直到這個數字的左邊數字比它還要小，就可以停止了。插入排序法主要的回圈有兩個變數：i和j，每一次執行這個回圈，就會将第i個數字放到左邊恰當的位置去。
1、從第一個元素開始，該元素可以認為已經被排序。 2、取出下一個元素，在已經排序的元素序列中從後向前掃描。 3、如果該元素（已排序）大于新元素，則将該元素移到下一位置。 4、重複步驟3，直到找到已排序的元素小于或者大于新元素的位置。 5、将新元素插入到該位置。 6、重複步驟2。
如果目标是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況如下。
最好情況：序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。
最壞情況：序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。
直接插入排序屬于穩定的排序，最壞時間複雜度為O(n^2)，最好時間複雜度為O(n)，空間複雜度為O(1)。
插入排序的指派操作是比較操作的次數加上(n-1)次。
是以，插入排序不适合對于資料量比較大的排序應用。
==================================================================================================
作者：歐陽鵬 歡迎轉載，與人分享是進步的源泉！