排序算法 | 直接插入排序算法的圖解、實現、復雜度和穩定性分析

---

目錄

• • • • • 1、直接插入排序定義
        • 2、直接插入排序,步驟說明
        • 3、動態圖演示
        • 4、代碼實現，運行結果
        • 5、算法分析
        • • ① 時間復雜度分析
          • ② 空間復雜度分析
          • ③ 算法穩定性

---

1、直接插入排序定義

直接插入排序（Straight Insertion Sort），是比較簡單的一種排序方式
直接插入排序的思想框架，簡單來說就是，從后面的未排序的序列中，拿一個元素出來，插入到前面的已經排序完成的有序的序列中去，插入適當的位置；后續的元素也是如此，一直到序列全部排序完畢；

2、直接插入排序,步驟說明

• 第一個元素，即可認為是已經有序的一個序列
• 取下一個未排序的元素，準備插入到前面有序序列當中
• 對于前面的有序序列，從后往前掃描
• 掃描到 大于等于 有序序列中元素的位置，插入在其后面

3、動態圖演示

這里，我們默認要求是排序一個升序的序列
現在，定義一個舉例數組，如下：

int arr[] = {3,44,38,15,47,43,15};

PS：我們需要關注一下，最后的元素 15

排序前：

排序中：

排序后：

可以看到，后續的 15 放在 第一個排好序的 15 的后面，根據步驟來

4、代碼實現，運行結果

① 代碼

void Straight_Insert_Sort(int *arr, int length) {int tmp;for (int i = 1; i < length; i++){tmp = arr[i];int j = i - 1; // 從后往前while (j >= 0 && arr[j] > tmp){arr[j + 1] = arr[j];j--;}}arr[j + 1] = tmp; // 滿足，插入}

② 結果：

5、算法分析

① 時間復雜度分析

最好的情況：O(n）；此時整個序列就是我們想要的升序；只需要比較 n - 1 次
最壞的情況：O(n^2）；此時整個序列就是我們不想要的逆序–降序；需要比較n(n-1)/2次
平均的情況：O(n^2）；

通過整個分析和直接插入排序的步驟，可以知道直接插入排序，不適合排序很大的數據

② 空間復雜度分析

O(1），因為沒有使用多余的空間

③ 算法穩定性

從剛剛提醒我們注意的 15 的放置位置可以看到，兩個相同的元素15 ，但是排序之后，再后面的15依舊在后，在前面的15 依舊在前，不會有位置的交換；
所以，直接插入排序是一種穩定的排序算法。

總結

以上是生活随笔為你收集整理的排序算法 | 直接插入排序算法的图解、实现、复杂度和稳定性分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。