??個人主頁：個人主頁
??系列專欄：C語言試題200例
??推薦一款刷算法、筆試、面經、拿大公司offer神器?? 點擊跳轉進入網站
?作者簡介：大家好，我是碼莎拉蒂，CSDN博客專家（全站排名Top 50），阿里云博客專家、51CTO博客專家、華為云享專家

1、題目

題目：實現排序算法

概念及其介紹
插入排序(InsertionSort)，一般也被稱為直接插入排序。

對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經排好序的有序表中，從而一個新的、記錄數增 1 的有序表

。在其實現過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，內層循環對當前元素前面有序表進行待插入位置查找，并進行移動。

時間復雜度
插入排序的平均時間復雜度也是 O(n^2)，空間復雜度為常數階 O(1)，具體時間復雜度和數組的有序性也是有關聯的。

插入排序中，當待排序數組是有序時，是最優的情況，只需當前數跟前一個數比較一下就可以了，這時一共需要比較 N-1 次，時間復雜度為 O(N)。最壞的情