插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1 /////////////////////////插入排序/////////////////////////
2 void InsertSort(int a[], int len)
3 {
4 int i, j;
5 int temp = 0;
6 for (i = 1; i < len; i++)
7 {
8 temp = a[i];
9 for (j = i; j>0 && a[j-1] > temp; j--)
10 {
11 a[j] = a[j-1];
12 }
13 a[j] = temp;
14 }
15 }
平均时间复杂度为O（n^2），最好的情况是O（n），即数组已经是有序状态，最差O（n^2），辅助存储为O（1）。插入排序是稳定的排序算法。
原文：https://www.cnblogs.com/cinvzi/p/9406531.html