直接插入排序

假设待排序序列为：49, 38, 65, 97, 76, 13, 27, 30，已经存储在数组Array中，采用插入法对这8个数按从小到大的顺序排序。

在直接插入排序法中，将Array[i]插入到一个合适的位置，采取的方法是：当左边的某个元素大于Array[i]时，将Array[i]与它交换；如此直到第一个小于Array[i]的元素为止。每次交换需要执行3条语句。

一个小小的优化方案是：先用一个临时变量TempRecord存储Array[i]，当左边的某个元素大于Array[i]时，将它后移一个位置，如此直到第一个小于Array[i]的元素为止，最后将TempRecord的值存放到该位置上。每次后移只需要1条语句。

优化的插入排序算法思想及执行过程详见下页中的图。

样例：

8
49 38 65 97 76 13 27 30
13 27 30 38 49 65 76 97

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>


using namespace std;


int main()
{
int n;
cin>>n;
int a[100];
a[0]=-1; //方便后面有更小的数字要插入第一格
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=2;i<=n;i++)
{
int temp=a[i];
for(int j=i-1;j>=1;j--)
{
//找到要插入的位置；且a[j-1]=a[0]时不会超出数组界限
if((a[i]<a[j])&&(a[i]>a[j-1]))
{
for(int k=i;k>=j+1;k--)
{
a[k]=a[k-1];
}


a[j]=temp;
}
}
}
for(int i=1;i<=n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}