目錄
一：插入排序——原理
二：插入排序——分析
三：插入排序——實現
四：插入排序——效率
一：插入排序——原理
????????插入排序的原理和基本思想：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列 。
動圖如下：??
二：插入排序——分析
選擇排序的核心就是：多趟選擇插入
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
通俗來講就是：以升序（從小到大）下列動圖排序為例，假若有N個數。
- 第一次插入：因為第0個位置可以看作已經排好序了，將array[1]（i ==1）看作是被插入的數據，即讓被插入的數據與 [ 0 , i ) 區間的元素數據相比，若遇到數據比 被插入的數據要大，遇到的數據后移一位，若遇到數據比 被插入的數據要小，就將被插入的數據插入到該數據的后面。這樣排好之后，前兩個數據就變得有序了。
- 第二次插入：i == 2，此時前兩個數據是有序的，即是將 array[2]看作是被插入的數據，在往前進行觀察選擇插入。
- ......
- 最后一次插入：i==N -1，此時前N-1個數據是有序的，將array[N-1]看作是被插入的數據，在往前進行觀察選擇插入。這一趟選擇插入之后，這整個數組序列就變得有序了。
三：插入排序——實現
#include<stdio.h>
// 插入排序
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++) // 決定所插入數據的位置 和 決定插入遍歷的次數 {int tem = a[i]; // 被插入的數據int end = i - 1; // 決定 與被插入的數據相比較 的區間while (end >= 0) // 結束條件：全部數據比較完成，該循環目的是：找到比被插入數據要小的值的位置{if (a[end] > tem) // 已排好的數組中end的位置上的數 比 所要插入的數 大就交換{a[end + 1] = a[end]; // 大數往后移一位end--; // end 往前走一步}else // 有數據比 被插入的數據要小，跳出循環{break;}}a[end + 1] = tem; // 將要插入的數插入到 end 位置的后一位。}
}int main()
{int a[] = { 29,10,14,37,12,6,32 };int sz = sizeof(a) / sizeof(a[0]); // 獲取數組的大小printf("插入排序：\n");for (int i = 0; i < n; i++) // 打印排序前的序列{printf("%d ", a[i]);}printf("\n");InsertSort(a, sz); // 執行 插入排序 函數for (int i = 0; i < n; i++) // 打印排序后的序列{printf("%d ", a[i]);}printf("\n");
}四：插入排序——效率
時間復雜度：O(N^2)
空間復雜度：O(1)
插入排序是一種穩定的排序。
當元素集合越接近有序，插入排序算法的時間效率越高。
????????以上的內容若是對大家起到幫助的話，大家可以動動小手點贊，評論+收藏。大家的支持就是我進步路上的最大動力！?
)
