一、插入排序
插入排序（Insertion-Sort）的算法描述是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。
1、算法描述
1. 從第一個元素開始，該元素可以認為已經被排序；
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描；
3. 如果該元素（已排序）大于新元素，将該元素移到下一位置；
4. 重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到該位置後；
6. 重複步驟2~5。
2、算法圖解
3、算法demo：
void insert_sort(vector<int> vec)
{
const int sz = vec.size();
int i, j;
for (i = 1; i < sz; ++i)
{
if (vec[i] < vec[i-1])
{
int temp = vec[i];
for (j = i - 1; j >= 0 && vec[j] > temp; --j)
{
//把最後面的數插入到前面合适的位置，如果目前值小于前面的值則交換，否則停止
//是以每次插入時，先前的資料總是有序的。
vec[j + 1] = vec[j];
}
vec[j + 1] = temp;
}
}
for (const auto v : vec)
cout << v << " ";
}
4、算法總結
插入排序是穩定排序。适用于大部分資料已經做過排序的情況或者已排序的資料庫新增資料後再進行排序。最好情況的時間複雜度為O（n），最壞情況為O（n^2）。插入排序在實作上，通常采用in-place排序（即隻需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。
二、插入排序的優化（二分插入排序）
上面的插入排序實作中，為了找到元素的合适的插入位置，我們采用從後到前周遊的順序查找進行比較，為了減少比較的次數，我們可以換種查找政策：采用二分查找。
1、算法demo：
//二分查找函數，傳回插入下标
int binarySearch(vector<int> vec, int start, int end, int key)
{
while (start <= end)
{
int middle = (start + end) / 2;
int middleData = vec[middle];
if (middleData > key)
end = middle - 1;
else
start = middle + 1;
}
return start;
}
//二分插入排序
void binary_insert_sort(vector<int> vec)
{
const int sz = vec.size();
int i, j;
for (i = 1; i < sz; ++i)
{
if (vec[i] < vec[i-1])
{
int temp = vec[i];
//使用二分查找在有序序列中進行查找，擷取插入下标
int index = binarySearch(vec, 0, i, vec[i]);
//移動元素
for (j = i - 1; j >= index && vec[j] > temp; --j)
{
vec[j + 1] = vec[j];
}
//插入元素
vec[index] = temp;
}
}
for (const auto v : vec)
cout << v << " ";
}
2、算法總結
二分查找的算法并不會因為等于某一個值而停止查找，它将查找整個序列直到start<=end條件不滿足而得到插入的位置，是以對于長度為n的數組來說，比較次數為logn ,時間複雜度為O（logn）。最好情況的時間複雜度為O（logn），最壞情況為O（n^2）。
三、希爾排序
1959年Shell發明，第一個突破O(n^2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優先比較距離較遠的元素。希爾排序又叫縮小增量排序。
1、算法描述
1. 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列個數k，對序列進行k 趟排序；
3. 每趟排序，根據對應的增量ti，将待排序列分割成若幹長度為m 的子序列，分别對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
2、算法圖解
3、算法demo：
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
vector<int> vec = { 63, 92, 27, 36, 45, 71, 58, 7 };
const int sz = vec.size();
int jump = sz / 2;//設定劃分數
while (jump != 0)
{
for (int i = jump; i < sz; ++i)
{
int tmp = vec[i];
int j = i - jump;
while (j >= 0 && tmp < vec[j])//插入排序
{
vec[j + jump] = vec[j];
j -= jump;
}
vec[j + jump] = tmp;//最小的元素放在最前面
}
jump /= 2;//劃分數每次減半
}
for (const auto v : vec)
cout << v << " ";
system("pause");
return 0;
}
4、算法總結
希爾排序是不穩定排序，适用于大部分資料已經做過排序的情況或者已排序的資料庫新增資料後再進行排序。最好情況的時間複雜度為O（n），最壞情況為O（n^2）。希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列，也可以動态的定義間隔序列。
參考：http://www.cnblogs.com/QG-whz/p/5194569.html
https://www.cnblogs.com/onepixel/articles/7674659.html