目錄

引言

一、直接插入排序的相關概念

1.1、基本概念

1.2、直接插入排序過程詳解

二、代碼實現

三、時間復雜度

四、希爾排序

4.1、希爾排序的陳述

4.2、代碼實現

4.3、時間復雜度

結語

---

引言

在計算機科學的世界里，排序算法是基礎且重要的組成部分。它們是組織和處理數據的核心工具，能夠讓數據更易于檢索、分析和理解。今天，我們將一同探討一種簡單而經典的排序算法——直接插入排序。 尤其對于初學者來說，理解直接插入排序的原理和實現，能夠幫助你更好地掌握C語言的編程技巧，并為后續學習更復雜的排序算法奠定堅實的基礎。本文將結合C語言代碼實例，帶你深入理解直接插入排序的原理、實現方法，并探討其優缺點，讓你能夠輕松掌握這一基礎算法。

一、直接插入排序的相關概念

1.1、基本概念

直接插入排序是插入排序的一種，其核心思想是：把待排序的序列，按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中。

通過核心思想，我們了解到，直接插入排序的前提條件是有一個有序序列，那么，我們還沒進行直接插入排序，難道就需要利用其他算法先排序一遍嗎？當然不是，這里有個很隱晦的條件——單個元素也是有序序列！是不是感覺有點牽強，但是仔細想想，也確實是這樣的。

1.2、直接插入排序過程詳解

通俗點說，就是先找出一個有序序列（單個元素，一般用首元素），然后依次遍歷后面的元素，然后在看看后面的元素適合放在哪個位置，就放在哪個位置

那么，具體的操作應該怎樣呢？

首先，我們要創建兩個變量，end 存放元素的下標，tmp存放的是下標對應的元素，而且，tmp 存放的元素是 arr[end+1] ，如圖：

其次，判斷 end 指向的元素 與 tmp 存放的元素比大小，如果比 tmp 大了，則 end 的元素覆蓋 end+1的元素，如圖：

直到 end 小于0為止。目前截止，這只是第一個循環，結束后，要將tmp的元素放到 arr[end+1] 中。

從第二循環開始， end 就等于 1 了，然后等于3 ，一直到倒數第二元素結束。

在上面的動圖循環完成后，end 將會變成3 ，開始下一輪的操作。一直到倒數第二個元素為止，因為tmp始終比end大一 ，又不能讓tmp越界訪問。

二、代碼實現

void InsertSort(int* arr, int n)
{assert(arr);for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}

代碼這里正常寫就行了，注意end的停止范圍，不能讓tmp越界訪問哦！

三、時間復雜度

通過上面代碼，可以看到有兩個循環，而且結合過程，就知道它把序列遍歷了兩遍，所以時間復雜度為 O(N^2)? ，當然，最好的情況就是序列本來就是有序或者近似有序的，則時間復雜度就變為O(N)。

四、希爾排序

前面提到，直接插入算法的時間復雜度為O(N^2) ,而只有在待排序列是有序的或者近似有序的時候，它的時間復雜度才能降為 O(N)。那么，有沒有什么辦法可以降低直接插入排序的時間復雜度呢？有的，那就是希爾排序

4.1、希爾排序的陳述

先選定一個整數，把帶待排序文件所有記錄分成各組，所有的距離相等的記錄分在同一組內，并對每一組內的記錄進行排序，然后 gap = gap/3 +1 得到下一個整數，再將序列分割成各組，進行插入排序。當 gap = 1時，就相當于直接插入排序

如圖，是 gap = 3 時的分組

將每組排完序后：

gap = 3/3 +1 = 2， 所以就是這樣分組的：

每組排好序后：

接下來的 gap = 2/3+1 = 1 ，也就是一個元素一組，相當于直接插入排序：

此刻再看，待排序序列已經成為一個近似有序序列，甚至是有序序列，這樣，時間復雜度只有O(N)！

4.2、代碼實現

void ShellSort(int* arr, int n)
{assert(arr);int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

這里要提一嘴，分組時的插入排序算法和直接插入排序算法是一樣的，區別就在于，直接插入排序元素是一個挨著一個的，而分組元素中間有個 gap ，，把gap看成1就是直接插入排序了。因此，分組的排序只需要在直接排序算法的基礎上把1改為gap就行了。

4.3、時間復雜度

有大佬說過希爾排序的時間復雜度非常復雜，但最后還是給出了具體的值：O(N^1.3)。鄙人水平有限，這里就不推導了。

可以看到，希爾排序的時間復雜度比直接插入排序的時間復雜度要小的很多，從某種意義上說，希爾排序即是一種新的排序，也是直接插入排序的延伸和改進！

結語

恭喜你，你已經掌握了C語言插入排序算法的核心知識！ 通過本文的學習，你不僅理解了直接插入排序的原理，還學會了用C語言實現它，并了解了它的優缺點。 掌握直接插入排序，是成為一名合格程序員的必經之路。希望你能夠將所學知識應用到實際項目中，不斷提升自己的編程能力。 記住，實踐是檢驗真理的唯一標準，多寫代碼，多思考，你就能在編程的世界里越走越遠！ 祝你在編程的道路上越走越好！