今天給大家簡單介紹一下插入排序。

插入排序，其基本思想是將未排序的數據逐步插入到已排序序列中的合適位置，從而使整個序列逐漸有序。

下面我們看一個排序的過程（升序），給定一個int類型的數組，利用插入排序的方法將這個數組排成升序。思想就是將第一個數據（或者已經有序的幾個數據如下圖的第2，3，4步）看成是有序的數據，然后利用后一個數據和前一個數據進行對比，若后一個數據比前一個大則不需要改變他們在數組的位置位置，若后一個數據比前一個數據大，那就將他們交換位置，一直循環比較下去直到數組排成升序或者降序。

看下圖，我們首先寫出假設數組已經有序的情況下的單趟插入排序：

給定一個數組元素為6，end為4，此時若插入為0，比較end位置的數據與0比較，0比end位置的數據小那么0放到end位置，end位置的數據8放到end+1（0的位置）然后end--，依次往前比較直到end<0時結束。若插入為9則不需要挪動數據。

下面為單趟排序代碼

int temp = arr[end + 1];// 保存end+1位置的數據以免后面被覆蓋了導致數據丟失
while (end >= 0)
{if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else// 不滿足則跳出循環{break;}
}
// 不管是循環結束還是break跳出都是往end+1處插入這個數據
arr[end + 1] = temp;

那現在給定一個亂序的數組，我們將第一個數據看成是有序數據，然后讓它和他后面一個數據進行比較，那么寫一個循環來重復此比較

// 插入排序
void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1;i++) // 注意結束條件{int end = i;// i=0為第一個數據int temp = arr[end + 1];// 保存end+1位置的數據以免后面被覆蓋了導致數據丟失while (end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}// 不管是循環結束還是break跳出都是往end+1處插入這個數據arr[end + 1] = temp;}
}

測試排序代碼

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>// 插入排序
void InsertSort(int* arr, int n)
{for (int i = 0;i < n - 1;i++) // 注意結束條件{int end = i;// i=0為第一個數據int temp = arr[end + 1];// 保存end+1位置的數據以免后面被覆蓋了導致數據丟失while (end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];end--;}else{break;}}// 不管是循環結束還是break跳出都是往end+1處插入這個數據arr[end + 1] = temp;}
}void Printarry(int* arr, int n)
{for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}void TestInsertSort() 
{int arr[] = { 3,1,4,2,8,4,9,6,0,7 };Printarry(arr, sizeof(arr) / sizeof(arr[0]));InsertSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{TestInsertSort();return 0;
}

結論：插入排序是一種簡單排序算法，其核心思想是將未排序元素逐個插入到已排序序列的正確位置。算法實現時，首先將第一個元素視為有序序列，然后依次將后續元素（temp）與已排序元素從后往前比較，若temp較小則后移已排序元素，直至找到合適位置插入。文中給出了單趟排序的實現代碼和完整插入排序函數，并通過測試用例驗證了算法的正確性，成功將無序數組{3,1,4,2,8,4,9,6,0,7}排序為升序序列。

PS：后面補充堆排序和二叉樹