1.直接插入排序
直接插入排序是一種最簡單的排序算法，它的基本操作是将一個記錄插入到已經排序好的序列中，進而得到一個新的有序表。直接插入排序算法原理如下圖所示：
直接插入排序算法如下：
void InsertSort(int arr[],int length)
{
int key,j;
for(int i=;i<length;++i)
{
key=arr[i]; //記錄标志;
j=i-;
//循環比較并且交換相鄰的兩個數;
while (j>=&&arr[j]>key)
{
arr[j+]=arr[j];
j=j-;
}
arr[j+]=key;
}
}
插入排序的算法複雜度分析：從空間的角度來看，它需要一個記錄的輔助空間，從時間的角度上來看，排序的基本操作：比較兩個關鍵字的大小和移動記錄。從算法中可以看出，for循環的次數取決于待插入關鍵字與前面i-1個關鍵字的關系。在整個排序過程中，當待排序的序列中記錄按關鍵字按從小到大正序排列時，隻需進行n-1次比較，比較次數達到最小值，記錄不需要進行移動。反之，當待排序的序列是按逆序進行排列時，總的比較次數達到了最大值（n+2）（n-1）/2。記錄移動的次數也達到了最大值（n+4）（n-1）/2。我們可以取最小值和最大值的平均值，則比較次數和移動記錄次數約為n^2/4。是以，直接插入排序的算法複雜度為O（n^2）插入排序中相同的元素排序前後的位置不會發生改變，是以直接插入排序是一種穩定的排序方式。
2.希爾排序
希爾排序又稱”縮小增量排序“它也屬于插入排序類方法，但在時間效率上較前述直接插入排序方法有較大的改進。在進行插入排序時，如果全部是正序時，其時間複雜度為O（n）。
是以，如果待記錄序列”基本有序“時，直接插入排序的效率可大大提高。希爾排序的基本思想：先将整個待排記錄序列分割成為若幹了子序列分别進行插入排序，待整個序列”基本有序“時，再對全體記錄進行一次直接插入排序。希爾排序的過程如下圖：
希爾排序的算法思路：先将要排序的一組記錄按某個增量d（n/2,n為要排序數的個數）分成若幹組子序列，每組中記錄的下标相差d.對每組中全部元素進行直接插入排序，然後再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，最後使用直接插入排序完成排序。
希爾排序算法描述如下：
void ShellSort(int arr[],int length)
{
int gap; //選擇希爾排序的步長;
//計算出希爾排序的次數;
for (gap = length / ; gap > ; gap = gap / )
{
//進行gap次排序;
for (int i = ; i < gap; i++)
{
//一次插入排序;
for (int j = i + gap; j < length; j = j + gap)
{
if (arr[j] < arr[j - gap])
{
int temp = arr[j];
int k = j - gap;
while (k>=&&arr[k]>temp)
{
arr[k + gap] = arr[k];
k = k - gap;
}
arr[k + gap] = temp;
}
}
}
}
}
希爾排序的算法複雜度計算是一個複雜的過程，到目前為止還未找到一種最好的”增量“序列函數。平均情況下希爾排序的算法複雜度為O（n^1.3）由于在希爾排序中會根據增量來進行局部排序，是以相同的元素在希爾排序前後位置會發生改變，是以希爾排序是一種不穩定的排序。
3.總結
排序算法是算法的基礎，隻有多了解算法的基礎，才會對算法有更深的了解，本篇部落客要是為了更加深入的了解排序算法中的插入排序，如果有什麼不妥之處，望大家多多指教。