1. 直接插入排序
直接插入排序：指每次從無序表中取出第一個元素，把它插入到有序表的合适位置，使有序表仍然有序。
具體方法：
第一趟比較前兩個數，然後把第二個數按大小插入到有序表中；
第二趟把第三個資料與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；
依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。 我們看一下排序簡要過程：
原序列：5 1 2 4 3
用一個小例子列舉一下排序過程：（含代碼步驟）
上述過程的代碼片：
代碼的核心是比較和後移，注意要将待定元素多存一份，因為後移時，會占據該元素的位置。
void DirectInsertionSort(int* a, int n)// 直接插入排序
{
for (int i = 0; i < n - 1; ++i)
{
int end = i;// 下标
int index = a[end + 1];// 記錄待定的值
while (end >= 0)
{
if (index < a[end])
{
a[end + 1] = a[end]; // 移動元素
--end;
}
else break;
}
a[end + 1] = index;// 插入待定值
}
}
總結
穩定性：穩定
時間複雜度：O(N2)
空間複雜度：O(1)
最好：順序O(N) 最壞：逆序O(N2)
元素序列越接近有序，直接插入排序算法的時間效率越高。2. 希爾排序
希爾排序：
對直接插入排序算法的優化。把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止。
具體方法：
首先确定一個正整數d1，使得d1<n，所有序号相隔d1的元素為一組，組内進行直接插入排序；
然後取d2<d1，重複上述分組和排序操作；
直至di=1,即所有記錄放進一個組中排序為止。
我們看一下排序簡要過程：
最常用的初始步長就是length/2。在這個例子中，length=9，是以初始步長gap=4。
1. 我們将原序列分成四組 (步長是多少就分多少組！)： 代碼實作：
void ShellSort(int* a, int n)// 希爾排序
{
int gap = n;
while (gap > 1)
{
//gap = gap / 2; // 一般情況下，gap是一半一半
gap = gap / 3 + 1;// 這種情況更好一點
for (int i = 0; i < n - gap; ++i)// 循環每個組都要進行直接插入排序
{
int end = i;
int index = a[end + gap];
while (end >= 0)
{
if (index < a[end])
{
a[end + gap] = a[end];
end = end - gap;
}
else break;
}
a[end + gap] = index;
}
}
}
總結
穩定性：不穩定
平均時間複雜度：O(nlogn)—O(N2)
空間複雜度：O(1)
上述代碼中gap=gap/2 ，最壞：O(N2)
還有 gap=gap/3+1 ，最好：O(N1.3- N2) 最壞：O(N2)
在此推薦一個部落格：https://blog.csdn.net/qq_39207948/article/details/80006224