之前寫過的排序文章，放上鏈接給大家看看。

C語言，誰都能看得懂的歸并排序

高中新生開學，需要進行軍訓，軍訓的時候，教官需要大家把按高到低排隊排好。

先隨機找到一個比較帥的男生做排頭。

然后第二個人過來跟這個男生比身高，如果比第一個高，就排到左邊，要不就排到右邊。

然后第三個人過來了，他需要在原來的兩個人中找到自己的位置。

……

經過把所有的人插入原來的序列，就完成了學生的身高排序。

—— 定義

插入排序顧名思義就是把未排序的數字插入到已經排序的序列的正確位置。

插入排序在很多文章中也會寫作直接插入排序。

——?用圖片來舉例子

比如我們需要排序這幾個數字

我們首先拿出第一個數字6。

然后我們取第二個數字和第一個數字6進行排序，6被認為是已經排序好的數列，因為它就只有一個數字，當然是排序好的了。

5和6排序后，可以得到新的數列

前面兩個已經是排序好的序列，再拿第三個序列和前面的序列比較。

然后新排序的序列會變成這樣

后面的數字都會依次插入前面已經排序好的序列，得到一個新的排序好的序列。

整個過程如下圖

—— 插入排序是否是穩定的排序算法？

什么是穩定排序？

如果兩個位置 A[j] == A[k]?相等，我們的排序算法不會改變 A[j] 和 A[k]的位置，這樣的排序算法就是穩定的。

比如下面的序列，我們把數字5插入到原來的序列中，但是原來的序列中也有一個數字5，我們不改變原來數字的位置，就說明是穩定的排序。

—— 代碼實現

#include???<stdio.h>void?insert_sort(int?arr[],?int?n) {int?i,j,temp;/*從第一個位置開始，1~n-1，依次和前面的數據比較*/for?(i?=?1;?i?<?n;?i++){/*保存要插入的值*/temp?=?arr[i];/*找到需要插入數據的位置*/for?(j?=?i?-?1;?temp?<?arr[j]?&&?j?>=?0;?--j){/*把j位置的數據移動到j+1位置，向后移動一位*/arr[j?+?1]?=?arr[j];}/*插入數據*/arr[j?+?1]?=?temp;} }#define?LENGTH?8int?main() {int?i,j;int?arr[LENGTH]?=?{6,5,3,1,8,7,2,4};/*排序前*/for(i=0;i<LENGTH;i++)printf("%d?",arr[i]);printf("\n");insert_sort(arr,LENGTH);/*排序后*/for(i=0;i<LENGTH;i++)printf("%d?",arr[i]);printf("\n");return?0; }

看代碼，是從第 1 位置開始做插入排序的，而且比較是從后往前開始比較。

比如第一個位置的數字，需要和第0個位置開始比較。

如果是第3個位置，就需要和第2、1、0這三個位置比較。

—— 代碼輸出

6?5?3?1?8?7?2?4? 1?2?3?4?5?6?7?8?

加上隨機數的代碼

#include???<stdio.h> #include??<stdlib.h> #include????<time.h>void?insert_sort(int?arr[],?int?n) {int?i,j,temp;/*從第一個位置開始，1~n-1，依次和前面的數據比較*/for?(i?=?1;?i?<?n;?i++){/*保存要插入的值*/temp?=?arr[i];/*找到需要插入數據的位置*/for?(j?=?i?-?1;?temp?<?arr[j]?&&?j?>=?0;?--j){/*把j位置的數據移動到j+1位置，向后移動一位*/arr[j?+?1]?=?arr[j];}/*插入數據*/arr[j?+?1]?=?temp;} }#define?LENGTH?30int?main() {int?i,j;int?arr[LENGTH]?=?{6,5,3,1,8,7,2,4};/*隨機數設置種子*/srand((unsigned)time(NULL));/*賦值*/for(i=0;i<LENGTH;i++)arr[i]?=?rand()%100;/*排序前*/for(i=0;i<LENGTH;i++)printf("%d?",arr[i]);printf("\n");insert_sort(arr,LENGTH);/*排序后*/for(i=0;i<LENGTH;i++)printf("%d?",arr[i]);printf("\n");return?0; }

—— 代碼輸出

58?90?36?55?5?91?27?56?19?37?69?75?73?24?14?2?40?57?27?86?2?31?6?59?23?92?16?10?62?92? 2?2?5?6?10?14?16?19?23?24?27?27?31?36?37?40?55?56?57?58?59?62?69?73?75?86?90?91?92?92?

—— 算法復雜度

老王帶你理解算法復雜度O(1),O(N),O(N^2)

時間復雜度和空間復雜度，一看就懂，面試前必過一遍

兩個循環遍歷，算法時間復雜度是?O(N^2)

---

推薦閱讀：

專輯|Linux文章匯總

專輯|程序人生

專輯|C語言

我的知識小密圈

關注公眾號，后臺回復「1024」獲取學習資料網盤鏈接。

歡迎點贊，關注，轉發，在看，您的每一次鼓勵，我都將銘記于心~

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的图解，C语言数据结构，插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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