1. 直接插入

基本思路：不斷地把 指針 i 指向的關(guān)鍵字插入到前面的有序序列，然后 i 指向無(wú)序序列的第一個(gè)關(guān)鍵字

1. 指針 i 指向第一個(gè)關(guān)鍵字
2. 指針往后移一位
3. 指針指向的關(guān)鍵字插入到 i 前面有序的序列中
   • 如果 a[i] > a[i + 1]，則不用修改順序
   • 如果 a[i] < a[i + 1]，則找到適合的位置插入，把所有后面的關(guān)鍵字往后移動(dòng)一位
4. 指針 i 指向下一位

void InsertSort(ElemType a[], int n)
{
    int i,j;
    for (i = 2; i <= n; i++)
    {
        if(a[i].key < a[i - 1].key) // 如果 i 大于 i - 1 的關(guān)鍵字，可以直接插入
        {
            a[0] = a[i];
            for (j = i - 1;a[0].key < a[j].key; j--) 
            {
                //在循環(huán)中，一邊對(duì)比，一邊把關(guān)鍵字后移
                //滿(mǎn)足條件則停止后移
                a[j + 1] = a[j];
            }
            a[j + 1] = a[0];
        }
    }
}

• 空間效率：O(n)
• 時(shí)間效率
  • 最好:O(n)，進(jìn)行n - 1次插入。最好情況，是序列本來(lái)就是有序的，因此，每次只需要把第 i 個(gè)關(guān)鍵字插入到前面的有序序列中就好了，不需查找插入位置
  • 最壞:O(n²)。最壞情況，完全逆序，每次要和前面所有的關(guān)鍵字作對(duì)比，把前面每個(gè)關(guān)鍵字后移。因此操作次數(shù)是，∑ ^{n - 1} (i - 1)² i = 1，2，3.....直到n - 1
  • 平均情況: 取最好，最壞情況的平均數(shù)，此時(shí)總的比較次數(shù)和總的移動(dòng)次數(shù)均為 n²/4

2. 折半插入

可見(jiàn)，插入排序都存在一個(gè)過(guò)程，先找到插入的位置（查找），插入。
直接插入的查找方式簡(jiǎn)單粗暴，直接逐一比對(duì)，直到找到合適的位置。折半插入的基本思路與直接插入一致，但是查找方式不同，是利用折半查找。
因此，時(shí)間復(fù)雜度，改變的只是查找插入位置的時(shí)間，從n次變成 log₂n

low = 1;high = i -1;
while(low < high)
{
    mid = (low + high) / 2;
    if(a[mid].key < a[0].key)
        low = mid + 1;
    else
        high = mid - 1; 
}

3. 希爾排序

• 基本思路：多次對(duì)整個(gè)序列分成多個(gè)不同，可能相互重疊的子序列進(jìn)行排序，使得整個(gè)序列順序不斷接近順序。
• 分組依據(jù)，設(shè)置初始間隔dk，不斷地改變dk，并每次根據(jù)間隔dk去訪問(wèn)整個(gè)序列，形成子序列，并排序。
• 每一趟子序列的排序使得整個(gè)序列越來(lái)越接近順序，同時(shí)每次減少dk使得子序列不斷變大，最終dk = 1的時(shí)候，所得子序列便是整個(gè)序列。

void ShellSort(ElemType a[], int n)
{
    for (dk = n/2; dk >= 1; dk = dk / 2)//不斷使得dk變小，初始dk以及變小方式都是沒(méi)有固定的
    {
        
        for (i = dk + 1; i <= n; i += dk)//對(duì)以dk劃分的子序列進(jìn)行直接插入排序
        {
            if (a[i].key < a[i - dk].key)
                a[0] = a[i];
                for (j = i -dk; j > 0 && a[0].key < a[j].key; j -= dk)
                    a[j + dk] = a[j];
                a[j + dk] = a[0];
        }
     }
}

• 空間效率:O(1)
• 時(shí)間效率:依賴(lài)于增量序列的函數(shù)。當(dāng)n在某個(gè)特定的范圍是，O(n^1.3)，最壞情況O(n²)
• 適用性：僅適用于順序存儲(chǔ)的線性表。（據(jù)說(shuō)，鏈表使用希爾排序由于鏈表的結(jié)構(gòu)關(guān)系結(jié)點(diǎn)排序的效率會(huì)拖得很慢。。。）