#include <iostream>
using namespace std;

void insert_sort(int a[],int n) //直接插入排序
{
    int i,j,temp;
    for(i=1;i<n;i++)  //需要选择n-1次
    {
        temp=a[i]; //暂存下标为i的数.下标从1开始,因为开始时，下标为0的数前面没有任何数，此时认为它是有序的
        for (j=i-1; j>=0 && temp<a[j]; j--)
        {
            a[j+1] = a[j]; //如果满足条件就往后挪,最坏情况：temp<a[0],他要放在最前面
        }
        a[j+1]=temp;  //找到下标为i的数的放置位置
    }
}

void print_arrray(int a[],int len)
{
    for(int i=0;i<len;i++)
    {
        cout << a[i] << " ";
    }
    cout<<endl;
}

int main() {
    int a[]={
  7,3,5,8,9,1,2,4,6};
    cout<<"before insert sort : ";
    print_arrray(a,9);
    insert_sort(a,9);
    cout<<"after insert sort:";
    print_arrray(a,9);
    return 0;
}