1.插入排序法（Insertion Sort）
对于少量元素的排序，插入排序是一种比较有效的算法。
举例：一个一维数组，{31,41,59,26,41,58}，想要通过插入排序实现从左到右非递减排列，常把该序列分为两部分（已排序列+未排序列）。
第一步：初步划分。
31|41,49,26,41,58
已排序列 | 未排序列
由于31只有一个数，所以排或不排是一样的，都是31.
第二步：比较（非递减排列）。
插入排序永远是相邻的两个数作比较。
首先将未排序列的第一个数与已排序列的最后一个数作比较，如果右边的数小于左边的数，则互换两个数的位置，而后左移到下一个相邻数对，继续比较，否则不动。
31|41,49,26,41,58
31,41|49,26,41,58
31,41,49|26,41,58
31,41,26,49|41,58
31,26,41,49|41,58
26,31,41,49|41,58
26,31,41,41,49|58
26,31,41,41,49,58 （排序完毕）
第三步：输出。
for循环按length输出。
时间复杂度（time complexity）：
采用双循环的方式：
1.在最优的情况下，即原序列已经是按序排好的了，此时，未排序列中的每个数只需要与它前一个数作一次比较就可以了，总共需要（N-1）次比较，时间复杂度为O(N)；
2.在最坏的情况下，即原序列完全按与要求的反向排列，此时，未排序列中的每个数都需要与已排序列中的所有数作比较，总共需要 [1+2+3+...+(N-1)]=N(N-1)/2 次比较，时间复杂度为O(N2)；
3.理论平均情况下，即每次已排序列最后一个数和未排序列第一个数构成相邻数对进行比较时，此时，一半的数比未排序列的第一个数大，一半的数比它小，这种情况中，比较次数仍是输入规模N的二次函数，时间复杂度与2中的最坏情况大致一样。
在《算法导论》一书中，假定每条伪代码的执行时间，通过计算排序算法进行排序所需要的总时间来讨论插入排序算法的时间复杂度，而非讨论比较次数。假定每条伪代码执行的时间都是一个常量，n条伪代码构成排序算法，同时假定每条语句分别运行c1,c2,...cn个常量时间，即不论第n条语句重复执行多少次，每一次执行需要的时间都是cn。（注：所谓常量时间也就是时间复杂度，不随输入数据的大小改变，这个时间往往是渐进的。）
计算得到的时间复杂度也是输入规模n的二次函数，但是n2的系数则由循环语句中的判断和赋值语句的常量时间决定，可见，插入排序算法的时间复杂度主要与输入规模n有关，也与计算机执行相应判断与赋值语句的常量时间有关。
C++代码实现：
#include<iostream>
using namespace std;
int insertion_sort(int *arr,int length) {
int tmp;
int i, j;
for (i = 1; i < length; i++) {
tmp = arr[i];
for (j = i - 1;j>=0; j--) {
if (arr[j+1] < arr[j]) {
//非递减排序，如果非递增，"<"改为">"
arr[j+1] = arr[j];
arr[j] = tmp;
}
}
}
for (i = 0; i < length; i++) cout << arr[i]<<" ";
return 0;
}
int main() {
int a[6] = { 31,41,49,26,41,58 };
insertion_sort(a, 6);
return 0;
}