插入排序基本原理：对于给定的一组元素，初始时假设第一元素自成一个有序序列，其余的元素为无序序列，其余的元素为无序序列；
接着从第二个元素开始，按照记录的大小依次将当前处理的元素插入到其之前的有序序列中，直到最后一个元素插入到有序序列中为止。
数组{38,65,97,76,13,27,49}
第一趟排序 插入38： [38] 65 97 76 13 27 49
第二趟排序 插入65：[38 65 ] 97 76 13 27 49
第三趟排序 插入97：[38 65 97 ] 76 13 27 49
第四趟排序 插入76：[38 65 76 97 ] 13 27 49
第五趟排序 插入13：[13 38 65 76 97 ] 27 49
第六趟排序 插入27：[13 27 38 65 76 97 ] 49
第七趟排序 插入49：[13 27 38 49 65 76 97 ]
class InsertionSort { public: int* insertionSort(int* A, int n) { for(int i=1;i<n;i++) { int temp = A[i]; int j; for(j=i;j>0;j--) { if(temp<A[j-1]) { A[j]=A[j-1]; } else { break; } } A[j]=temp; } return A; } };
原文：http://www.cnblogs.com/omelet/p/6596870.html