概述：
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
思路：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。（此处没设置哨兵）
时间复杂度为：O(n2)
代码：
//直接插入排序
#include <iostream>
using namespace std;
void Print(int array[],int length){ //自定义输出函数，每执行一次打印一次序列
for(int i=0;i<length;i++){
cout<<array[i]<<" ";
}
cout<<endl;
}
void InsertSort(int array[],int length){
for(int i=1;i<length;i++){ //第1个数是有序的，所以从第2个数开始遍历，依次插入
int j=i-1; //前i-1个数都是有序序列(由小到大)，只要a[j]比temp大，就将此数后移
int temp=array[i];
for(j=i-1;j>=0&&array[j]>temp;j--){//a[j]小于 temp 时循环结束，结束后应将 temp 赋值给a[j+1]
array[j+1]=array[j]; //将 a[j] 后移一位
}
array[j+1]=temp; //将 temp 赋值给a[j+1]
Print(array,length);
}
}
int main(){
int array[]={49,38,65,97,76,13,27,49};
int length=sizeof(array)/sizeof(*array);
Print(array,length); //先打印原始序列
InsertSort(array,length);
return 0;
}运行结果：
