基本思想：
每步将一個待排序的對象，按其關鍵碼大小，插入到前面已經排好序的一組對象的适當位置上，直到對象全部插入為止。
即邊插入邊排序，保證子序列中随時都是排好序的。
基本操作：有序插入
在有序序列中插入一個元素，保持序列有序，有序長度不斷增加
起初，a[0]是長度為1的子序列。然後，逐一将a[1]至a[n-1]插入到有序子序列中
有序插入方法：
在插入a[i]前，數組a的前半段a[0]至a[i-1]是有序段，後半段a[i]至a[n-1]是停留于輸入次序的無序段
插入a[i]使a[0]至a[i-1]有序，也就是要為a[i]找到有序位置j（0<=j<=i），将a[i]插入在a[j]的位置上
插入位置圖示：
1.插在中間
2.插在最前面
3.插在最後面
如何找到插入位置呢？
1.順序法定位插入位置 --- 直接插入排序
2.二分法定位插入位置 --- 二分插入排序
3.縮小增量多遍插入排序 --- 希爾排序
（1）直接插入排序 -- 采用順序法查找法查找插入位置
因每次都需要判斷j是否越界，浪費時間消耗，是以可選擇采用了哨兵模式進行改進。哨兵避免了每次都要判斷越界的步驟。
（2）直接插入排序，使用哨兵
直接插入排序 --- 性能分析
實作排序的基本操作有兩個：
（1）‘比較’序列中兩個關鍵字的大小
（2）‘移動記錄’
最好的情況（關鍵字在記錄序列中順序有序）：
11、 25、 32、 47、 56、 70、 81、 85、 92、 96
‘比較次數’：n-1 '移動次數'：0
最壞情況（關鍵字在記錄序列中逆序有序）
96、92、85、81、70、56、47、32、25、11
‘比較’次數：1+2+3+......+n-1 =
‘移動’次數：
時間複雜度結論：
原始資料越接近有序，排序速度越快
最壞情況下，（輸入資料是逆有序） Tw(n) = O(n^2)
平均情況下，耗時差不多是最壞情況的一半 Te(n) = O(n^2)
要提高查找速度
減少元素的比較次數
減少元素的移動次數