1、算法原理
// 排序一个大小为n的数组arr[]，insertionSort(arr, n)i从1到n-1逐步变大
将元素arr[i] 插入到有序序列 arr[1...i-1]中
2、举个例子来说明算法：
需要排序的序列为：
4,3,2,10,12,1,5,6
3、第一步，由于第二个元素3小于第一个元素4。将元素3插入到元素4的前面。
4、第二步：将第三个元素2，插入到序列3,4 中。2插入第一个位置，3,4分别往后移动一位。
5、剩下的插入步骤与第一步和第二步类似，我们展示在下面，并不细讲
6、这一步提供算法实现的代码。
#include <iostream>
using namespace std;
void insertsort(int arr[],int n)
{
int i,j,key;
for (i=1;i<n;i++)
{
key=arr[i];j=i-1;
while (j>=0&&arr[j]>key)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
void printarray(int arr[],int n)
{
for (int i=0;i<n;i++)
{
cout<<arr[i]<<endl;
}
}
int main()
{
int arr[]={9,3,2,1,5,13,4};
int n=sizeof(arr)/sizeof(int);
insertsort(arr,n);
printarray(arr,n);
return 0;
}
