插入排序：
插入排序的思路也很简单：假设前面已经有i节点是有序的，那么就从第i+1个节点开始，插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的，因此从第2个开始，不断插入前面的有序序列，直到全部排列完毕。
假设总共有n个节点，那么总共需要将n−1个节点插入到有序序列中，而插入节点时需要找到合适的位置，显然这个查找的过程时间复杂度是O(n−i)，因此插入排序的时间复杂度是O(n−1)(n−i)，即O(n^2)。
原始数据（80，50，20，30，2，18，100）
第一次排序：（50，80，20，30，2，18，100）
第二次排序：（20，50，80，30，2，18，100）
第三次排序：（20，30，50，80，2，18，100）
第四次排序：（2，20，30，50，80，18，100）
第五次排序：（2，18，20，30，50，80，100）
代码：（第一种方法）
void Insertsort(int data[], int len) { int i, j; int temp; //插入排序 for (i = 1; i < len; i++) { temp = data[i]; //备份 //循环比较插入到指定位置 for (j = i; j > 0; j--) { if (data[j] < data[j - 1]) { data[j] = data[j - 1]; data[j - 1] = temp; } else break; } } }
代码：（第二种方法）
//就是默认第一个是有序的，后边是无序的，把后边无序的每个数插入到前面有序中，有序的越来越多，无序的越来越少。 //先找到有序数列的位置，然后插进去再把后边的数后移 void Insertsort1(int data[], int len) { //1.把无序的数找到在有序数列的位置 //0~i-1是无序的，i~是有序的 int i, j, k; int temp; for (i = 1; i < len; i++) { //i是无序数列中第一个数，遍历有序数列 for (j = 0; j < i; j++) { //找到位置了,j就是要插入的位置下标 if (data[i] < data[j]) { //k = j; temp = data[i]; //把j后边的数往后挪 /*for (; j < len; j++) data[j+1] = data[j];*/ for (k = i - 1; k >= j; k--) //a[j] ~ a[i-1]所有的元素往后挪动一位 { data[k + 1] = data[k]; } data[j] = temp; } } } }
