插入排序法是我們第一個學習到的排序方法，我們本篇會針對它來詳細的介紹一下。
- 插入排序法的原理
- 插入排序法的執行效能
javascript演算法實作
插入排序法的原理
我們先來看看下圖，來理論一下它是著麼進行排序，該圖來源為此interactivepython。
首先，我們會將資料分成兩部份，已排序與未排序，然後我們會進行以下作業
將已排序資料與後一個資料進行比較，如果已排序資料大於它，則進行位移
我們下面將以前四行來進行說明。注意，下列的 A[0] 代表陣列的第一個位置。
- 第一行 : 已排序資料為
54，然後我們與後一個26進行比較，54大於26因此我們會將26的位置替換成54，並將26插入至54的原位，結果為第二行。 - 第二行 : 已排序資料為
26、54，然後我們與後一個93進行比較，54小於93因此不用進行位移，因為26、54為已排序資料，因此只需要比較54就好，結果為第三行。 - 第三行 : 已排序資料為
26、54、93，然後與17進行比較，首先93大於17因此將93位移置A[3]，則時還沒插入喔，還要繼續比較，接下來54大於17因此將54位移至A[2]，然後26大於17，因此將26位移至A[1]，最後在將17插入剩餘的空間A[0]，結果為第四行。 - 第四行 : 已排序資料為
17、26、54、93，開始與77進行比較，93大於77因此將93位移至A[4]的位置，然後54小於77，因此54不需要位移，最後將77插入至空缺的位置A[3]，當果為第五行。
插入排序法的執行效能
那這個排序演算法效能如何 ? 我們會分成最好與最壞與平均來看。
最好狀況
O(n)
該演算法最好的情況是時間複雜度為O(n)，假設我們有下列陣列要排序。
[ 1 , 2 , 3 , 4 ]
我們一看就知道，他不用進行排序，但演算法還不知道，所以它至少還是要跑個for迴圈，跑個4次，才知道它不用排序，因為我們這時最好的狀況就是只要跑4次，也就是陣列的大小。
最壞狀況
O(n^2)
假設我們要下列陣列要排序。
[ 4 , 3 , 2 , 1 ]
對就是完全相反的，我們首先要跑for迴圈，然後裡面還要一個while比較，而且因為我們的陣列是完全相反的。
平均狀況
O(n^2)
我也不知道為啥平均是O(n^2)，真的。
建議使用情況
- 要排序的資料數量不大 : 平均是時間複雜度是
O(n^2)，如果來個1百萬個 n，你看看會如何。 - 大部份的資料已排序 : 上面有說過，該演算法會將資料分成已排序與未排序的來進行比較，也就是說如果已排序的資料越多，你就可以少做越少的比較。
javascript演算法實作
我們來看看它的演算法，我們採用javascript來進行撰寫。
function insertionSort(arr) {
if (!Array.isArray(arr))
throw 'elements is not array';
var len = arr.length;
var i = 0,
value = 0;
for (var pos = 1; pos < len; pos++) {
i = pos - 1;
value = arr[pos]; //正在處理的值
//判斷是否移位
while (i >= 0 && arr[i] > value) {
arr[i + 1] = arr[i];
i--;
}
// 插入新值
arr[i + 1] = value;
console.log(arr);
}
}
簡單的測試一下。
insertionSort([3,54,24,33,22,58,95,1,2,31])
