前幾章講了選擇排序中的直直接選擇排序、雙向選擇排序、堆排序，這次來講講利用‘插入’為核心來實作的插入排序算法。
插入排序
把待排序的記錄按其關鍵碼值的大小逐個插入到一
個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
其實在我們的生活中，插入排序是随處可見的
例如打撲克牌時我們将發來的卡牌一張一張的插入進排序好的手牌中。整理圖書或者檔案時按照編号将新的書籍放入已排序号的書架。這就是插入排序的核心 “将未排序資料一個個插入進已排序的資料中”
直接插入排序
直接插入排序就是對這個思路的簡單應用，例如對于下面這個資料，對其排升序。
如果要了解一個排序算法，我們首先要了解他的一趟思路。
對于上面這個資料，因為我們要排升序，按照前面的思路我們需要将未排序數列插入進已排序數列。紅框框起來的地方就是按照升序排序好的序列，此時，因為74的下一個資料53比他小，是以我們要将他插入進這個已排序的數列中，并且在已排序的數列中找到合适的位置。
因為53比74小，是以往前移動， 然後46比53小，是以在46前停下，然後将74放到原本53的位置，形成新的有序資料。
第二趟
然後因為14比74小，将其插入進有序數列中，因為14比有序數列中的任何數都小，是以通過比較大小，然後被放到了數組最前端，然後将74放到原本14的位置。
總結下來就是将數列中已經排好的有序子串以此與後面的對比，然後将其插入到合适的位置。
這是一趟的思路，而多趟無非就是不斷重複這個過程，直到排序結束。因為排N個資料，是以最壞情況下隻需将n-1個資料插入就可以排序成功。
是以下面開始代碼實作
void InsertSort(int* arr, int n)
{
int i, end, temp;
for(i = 0; i < n - 1; i++)
{
end = i;
temp = arr[end + 1];
//将插入元素儲存下來， 從有序子串的尾部開始對比插入
while(end >= 0)
{
if(arr[end] > temp)
{
arr[end + 1] = arr[end];
end--;
//如果插入的資料比這個位置的資料大，則比該資料大的資料後移，插入資料繼續往前直到找到比他小得資料後停下
}
else
break;
}
arr[end + 1] = temp;
//将插入的元素放到最終所在的位置
}
}
每趟排序
直接插入排序
時間複雜度：平均情況：O(n) 最好情況O(n^2) 最壞情況O(n^2)
空間複雜度：O(1)
希爾排序
希爾排序是對直接插入排序的改進，也是最高效的插入排序。
他的核心就是一種分組預排序的思路:
1.預排序
2.直接插入排序
就是用gap分組預排序，再對每一組插入排序
什麼意思呢？希爾排序引入了一個變量，gap(步長)，将間隔為gap的元素分為一組，對每一組進行插入排序，然後不停減少gap的大小，既每次擴大分組，在部分有序的基礎上再次進行分組插入排序，知道gap=1也就是隻剩下一個分組時，排序完成
還是剛剛那些資料
關于gap的選擇
gap越大，越不接近有序，跳的越快
gap越小，越接近有序，跳的越慢
為了剛開始快速預排，是以一開始我們需要将gap設定大一點，實作部分有序，然後逐漸減少，實作全體有序。
一般gap = length / 3 + 1;
還是那句老話，了解排序首先了解單趟。
為了友善觀看我将所有分組按照顔色不同來劃分
首先46大于間隔gap的26，将這個分組内的26插入到46前。
下面同理
然後到交換後的46也就是第5個位置時，将27插入到子序列，26 ，46中的合适位置。
下面同理
說白了，就是對每一個gap間隔的分組進行插入排序，在将每個相同顔色的子序列都排成有序，就是這一趟的目的。
這就是第一趟全部跑完後的結果，所有顔色的子序列已經全部有序
第二趟
gap = 2
還是上面的思路，每一種顔色對應的子序列排序。
排完後
最後一趟 gap = 1
沒有間隔，對所有資料進行插入排序，因為資料已基本有序，是以這一趟會特别快
排序結果
下面來進行代碼實作
void ShellSort(int* arr, int n)
{
int gap = n, i;
//當gap = 1時說明隻剩下一組，并且最後一組已排序，數組排序結束
while(gap > 1)
{
gap = gap / 3 + 1;
//每趟減少gap
for(i = 0; i < n - gap; ++i)
{
int end = i;
int temp = arr[end + gap];
while(end >= 0)
{
if(arr[end] > temp)
{
arr[end + gap] = arr[end];
end -= gap;
}
else
break;
}
arr[end + gap] = temp;
}
}
}
上面的代碼和直接插入排序極為相似，因為底層的核心思想還是直接插入排序，隻需要将原來的步長1改為gap即可實作，當外層gap=1時說明内層gap為1的分組已經排序結束，數組已有序。
全部排序
希爾排序
時間複雜度：平均情況：O(n) 最好情況O(n^1.3) 最壞情況O(n^2)
空間複雜度：O(1)