//直接插入排序

include[HTML_REMOVED]

using namespace std;

void insertsort(int data[],int n){
for(int i=2;i<=n;i++)//从第二个元素开始向前插入
{
if(data[i][HTML_REMOVED]data[0]){//一直和前面的元素对比
data[j+1]=data[j];//前面的元素向后移动
j–;//下一个
}
data[j+1]=data[0];//j是<=我，所以我放在j+1
}
}
}

int main()
{
int data[]={100,1,3,5,7,9,2,4,6,8,0};
insertsort(data,10);
for(int i=1;i<=10;i++)
cout<<data[i]<<’ ‘;
}

//分析
//最好情况，元素有序，那么只会判断n-1次，无移动O（n）
//最坏情况，逆序，每次比较1,2…n-1(无哨兵)，2,3,…n(有哨兵)
// 移动1,2,…n-1,时间复杂度n²

//空间O(1)
//适合n比较小，元素基本有序
//稳定，只有data[j]>data[i]才移动
//稳定性结合代码分析，不稳定性结合具体例子

//顺序存储可以，链式存储可以