每趟将一個待排序的對象，按其關鍵碼大小，插入到前面已經排序好的一組對象的适當位置
上，直到對象全部插入為止。
即邊插入邊排序，保證子序列中随時都是排好序的
插入排序算法的分類
排序過程：整個排序過程為n-1趟插入，即先将序列中第1個記錄看成是一個有
序子序列，然後從第2個記錄開始，逐個進行插入，直至整個序列有序。
void insertsort（sqlist &l）
{
int i，j；
設對象個數為n，則執行n-1趟
比較次數和移動次數與初始排序有關
每趟隻需要比較1次，不移動
總比較次數為n-1
若出現各種可能排序的機率相同，則可取最好情況和最壞情況的平均情況
平均情況比較次數和移動次數為n*n/4
時間複雜度為o(n*n)
空間複雜度為o(1)
是一種穩定的排序方法
折半插入排序建立在直接插入排序的基礎上，是它的拓展出來的東西.
我們在将一個新元素插入已經排好序的數組的過程中，尋找插入點時，将待插入
區域的上限設定為a[low],下限設定為a【high】,然後将待插入元素與區間中間
位置a[m]進行比較，其中m=（low+high）/2
如果比中間位置a[m]小，則選擇a[low]到a[m-1]為新的插入區域(即high=m-1)，
如果比中間位置a[m]大，則選擇a[m+1]到a[high]為新的插入區域(即low=m+1)
(3)如此直至low<=high不成立，即将此位置之後所有元素後移一位，并将新元素插入a[high+1]
折半查找比順序查找快，是以折半插入排序就平均性能來說比直接插入排序要快
它所需要的關鍵碼比較次數與待排序對象序列的初始化排列無關，僅依賴于對象個數。在插入第i個對象時，需要經過log2i+1次關鍵碼比較，才能确定它應插入的位置
當n較大時，總關鍵碼比較次數比直接插入排序的最壞情況要好得多，但其最好的情況要差
在對象的初始排列已經按關鍵碼排好序或接近有序時，直接插入排序比折半
插入排序執行的關鍵碼比較次數要少
折半插入排序的對象移動次數與直接插入排序相同，依賴于對象的初始排列
減少了比較次數，但沒有減少移動次數
平均性能優于直接插入排序
隻能用于順序結構，不能用于鍊式結構
适合初始記錄無序，n較大的情況
希爾排序是1959年由d.l.shell提出來的，相對直接插入排序有較大的改進。希爾排序又叫縮小增量排序。
直接插入排序在基本有序時，效率較高
在待排序的記錄個數較少時，效率較高
先将整個待排記錄序列按某個增量d分割成若幹組子序列，每組中記錄的下标
相差d，分别對每組進行直接插入排序，然後再用一個較小的增量對它進行分
組，在每組中再進行直接插入排序。這樣當經過幾次分組排序後，待整個序
列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。
子序列的構成不是簡單地“逐段分割”将相隔某個增量dk的記錄組成一組子序
列讓增量dk逐趟縮短（例如依次取5，3，1）
直到dk=1為止。
小元素跳躍式前移
最後一趟增量為1時，序列已基本有序