零、📃前言

??養成 「經常思考」 的習慣，在面臨難題的時候，才能臨危不亂，泰山崩于前而面不改色，
??這篇文章中，我會著重講解一些常見的 「演算法和資料結構」 的設計思想，并且配上動圖，希望讀者能夠帶上自己的 「思考」，主要針對面試中常見的問題和新手朋友們比較難理解的點進行決議，當然，這個系列的文章，后面也會給出面向演算法競賽的提綱，如果有興趣深入學習的歡迎在「評論區留言，一起成長交流」 ，

• 零基礎學演算法的最好方法，莫過于刷題了，當然，刷題是不夠的，刷的程序中也要多多總結，多多思考，養成 「經常思考」 的習慣，這就是所謂的 「 流水不腐，戶樞不蠹 」，任何事情都是需要堅持的，刷題也一樣，沒有刷夠足夠的題，就很難做出系統性的總結，所以上大學的時候，我花了三年的時間來刷題， 作業以后還是會抽點時間出來刷題，

千萬不要用作業忙來找借口，時間擠一擠總是有的，

• 當然，每天不需要花太多時間在這個上面，把這個事情做成一個規劃，按照長期去推進，反正也沒有 KPI 壓力，就當成是作業之余的一種消遣，還能夠提升思維能力，

所以，無論你是 小學生，中學生，高中OIer，大學ACMer，職場人士，只要想開始，一切都不會太晚！

??「 插入排序 」 是比較好理解且編碼相對簡單的排序演算法，雖然效率不是很高，但一般也出現在各種 「資料結構」 的教科書上，于是，我來了，我會盡量做到「深入淺出」，讓 90% 的 「零基礎小白 」 也都能理解，真正做到 「讓天下沒有難學的演算法」 ，我知道這很難，但是我愿意嘗試！我會盡量把文章寫得有趣，希望讀者朋友給個面子，幫我完成閱讀，不能完讀，我可就完犢子了 🤣，當然，如果你覺得還可以，給我個「 贊 」 和 「 收藏 」，這個對我很重要，謝謝了！

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌

那么，我的教程和別人的教程有什么不同的地方呢？
??「第一步」簡單釋義： 我會簡單解釋一下這個演算法的目的、思想、以及為什么叫這個名字以幫助記憶，
??「第二步」核心思想： 我會大致介紹一下這個演算法的核心思想，
??「第三步」動圖演示： 我會引入一個動圖，并且用一個切實的例子展示一下演算法執行的全程序，
??「第四步」演算法前置： 在學習這個演算法之前，我們需要學習的前置內容有哪些？這些內容是需要事先去攻克的，
??「第五步」演算法描述： 細致的講解整個演算法的執行流程，
??「第六步」演算法分析： 對演算法的時間復雜度和空間復雜度進行一個詳細的分析，
??「第七步」優化方案： 介紹一些可以優化的點，
??「第八步」代碼實踐： 用 C/C++ 來實作上述演算法，
??「第九步」代碼驗證： 最后，我會推薦一些比較好用的在線評測系統來驗證我們實作的演算法的正確性，

一、🎯簡單釋義

1、演算法目的

??將原本亂序的陣列變成有序，可以是 「升序」 或者 「降序」 （為了描述統一，本文一律只討論 「 升序」 的情況），

2、演算法思想

??通過不斷將當前元素 「插入」 到 「升序」 序列中，直到所有元素都執行過 「插入」 操作，則演算法結束，

3、命名由來

??每次都是將元素 「插入」 到 有序 序列中，故此命名 「 插入排序 」 ，

二、🧡核心思想

• 「迭代」：類似的事情，不停地做，
• 「比較」：關系運算子 小于等于( ≤ \le ≤) 的運用，
• 「移動」：原地后移元素，

三、🔆動圖演示

1、樣例

• 初始情況下的資料如 圖二-1-1 所示，基本屬于亂序，純隨機出來的資料，

2、演算法演示

• 接下來，我們來看下排序程序的影片演示，如 圖二-2-1 所示：

3、樣例說明

??我們看到，首先需要將 「第二個元素」 和 「第一個元素」 進行 「比較」，如果 前者 小于等于 后者，則將 后者 進行向后 「移動」，前者 則執行插入；
??然后，進行第二輪「比較」，即 「第三個元素」 和 「第二個元素」、「第一個元素」 進行 「比較」， 直到 「前三個元素」 保持有序 ，
??最后，經過一定輪次的「比較」 和 「移動」之后，一定可以保證所有元素都是 「升序」 排列的，

四、🌳演算法前置

1、回圈的實作

• 這個演算法本身需要做一些「 回圈 」進行迭代計算，所以你至少需要知道「 回圈 」 的含義，這里以 「 c++ 」 為例，來看下一個簡單的「 回圈 」是怎么寫的，代碼如下：

int n = 520;
for(int i = 0; i < n; ++i) {
    // TODO ： ，，，
}

• 這個陳述句就是一個最簡單的回圈陳述句，它會將回圈體內的陳述句執行 n n n 次，而這里的 n n n 等于 1314 1314 1314，也就是會執行 1314 1314 1314 次，

2、比較的實作

• 「比較」兩個元素的大小，可以采用關系運算子，本文我們需要排序的陣列是按照 「升序」 排列的，所以用到的關系運算子是 「小于等于運算子（即 <=）」 ，
• 我們可以將兩個數的「比較」寫成一個函式smallerEqualThan，以 「 c++ 」 為例，實作如下：

#define Type int
bool smallerEqualThan(Type a, Type b) {
    return a <= b;
}

• 其中Type代表陣列元素的型別，可以是整數，也可以是浮點數，也可以是一個類的實體，這里我們統一用int來講解，即 32位有符號整型，

3、移動的實作

• 所謂「移動」，其實是將某個元素執行后移，實作如下：

a[j + 1] = a[j];

五、🥦演算法描述

1、問題描述

??給定一個 n n n 個元素的陣列，陣列下標從 0 0 0 開始，采用「 插入排序 」將陣列按照 「升序」排列，

2、演算法程序

整個演算法的執行程序分以下幾步：
??1） 回圈迭代變數 i = 1 → n ? 1 i = 1 \to n-1 i=1→n?1；
??2） 每次迭代，令 x = a [ i ] x = a[i] x=a[i]， j = i ? 1 j = i-1 j=i?1，回圈執行比較 x x x 和 a [ j ] a[j] a[j]，如果產生 x ≤ a [ j ] x \le a[j] x≤a[j] 則執行 a [ j + 1 ] = a [ j ] a[j+1] = a[j] a[j+1]=a[j]，然后執行 j = j + 1 j = j + 1 j=j+1，繼續執行 2）；否則，跳出回圈，回到 1），

六、🧶演算法分析

1、時間復雜度

• 我們假設 「比較」 和 「移動」 的時間復雜度為 O ( 1 ) O(1) O(1)，
• 「 插入排序 」 中有兩個嵌套回圈，

外回圈正好運行 n ? 1 n-1 n?1 次迭代， 但內部回圈運行變得越來越短：
??當 i = 1 i = 1 i=1，內層回圈 1 1 1 次「比較」操作，
??當 i = 2 i = 2 i=2，內層回圈 2 2 2 次「比較」操作，
??當 i = 3 i = 3 i=3，內層回圈 3 3 3 次「比較」操作，
??……
??當 i = n ? 2 i = n-2 i=n?2，內層回圈 n ? 2 n-2 n?2 次「比較」操作，
??當 i = n ? 1 i = n-1 i=n?1，內層回圈 n ? 1 n-1 n?1 次「比較」操作，

• 因此，總「比較」次數如下：
• 1 + 2 + . . . + ( n ? 1 ) = n ( n ? 1 ) 2 1 + 2 + ... + (n-1) = \frac {n(n-1)}{2} 1+2+...+(n?1)=2n(n?1)?
• 總的時間復雜度為： O ( n 2 ) O(n^2) O(n2)

2、空間復雜度

• 由于演算法在執行程序中，只有「移動」變數時候，需要事先將變數存入臨時變數x，而其它沒有采用任何的額外空間，所以空間復雜度為 O ( 1 ) O(1) O(1)，

七、🧢優化方案

??「 插入排序 」在眾多排序演算法中效率較低，時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，
?? 想象一下，當有 n = 1 0 5 n = 10^5 n=105 個數字， 即使我們的計算機速度超快，并且可以在 1 秒內計算 1 0 8 10^8 108 次操作，但冒泡排序仍需要大約一百秒才能完成，
??考慮，在進行插入操作之前，我們找位置的程序是在有序陣列中找的，所以可以利用「二分查找」 來找到對應的位置，然而，執行 「 插入 」 的程序還是 O ( n ) O(n) O(n)，所以優化的也只是常數時間，最壞時間復雜度是不變的，

• 「改進思路」執行插入操作之前利用 「 插入 」 來找到需要插入的位置，

八、💙代碼實踐

#include <stdio.h>

int a[1010];

void input(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
}

void output(int n, int *a) {
    for(int i = 0; i < n; ++i) {
        if(i)
            printf(" ");
        printf("%d", a[i]);
    }
    puts("");
}

void InsertSort(int n, int *a) {       // (1)
    int i, j; 
    for(i = 1; i < n; ++i) {
        int x = a[i];                  // (2)
        for(j = i-1; j >= 0; --j) {    // (3)
            if(x <= a[j]) {            // (4)
                a[j+1] = a[j];         // (5)
            }else
                break;                 // (6)
        }
        a[j+1] = x;                    // (7)
    }
} 

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        input(n, a);
        InsertSort(n, a);
        output(n, a);
    }
    return 0;
} 

• ( 1 ) (1) (1) void InsertSort(int n, int *a)為 插入排序 的實作，代表對a[]陣列進行升序排序，
• ( 2 ) (2) (2) 此時a[i]前面的 i-1個數都認為是排好序的，令x = a[i]；
• ( 3 ) (3) (3) 逆序的列舉所有的已經排好序的數；
• ( 4 ) (4) (4) 如果列舉到的數a[j]比需要插入的數x大，則當前數往后挪一個位置；
• ( 5 ) (5) (5) 執行挪位置的 O ( 1 ) O(1) O(1) 操作；
• ( 6 ) (6) (6) 否則，跳出回圈；
• ( 7 ) (7) (7) 將x插入到合適位置；

九、💗代碼驗證

• 比如，你可以在百度上搜索 代碼在線提交、OnlineJudge、LeetCode、洛谷、HDOJ、POJ 等等的關鍵詞，然后去找對應的題目提交驗證你的代碼的正確性，

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《資料結構入門》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌