#include <bits/stdc++.h>
using namespace std;
int a[100005],n;
void charu()
{
  for(int i=1;i<n;i++)
  {
    int key=a[i];  //key表示要排序的数字的数值
    int j=i-1;    //j表示前面已排序好的数的个数
    while(j>=0&&key<a[j])
    {
      a[j+1]=a[j];  //把a[j]往后挪
      j--;
    }
    a[j+1]=key;
  }
}
int main(){
cin>>n;
for(int i=0;i<n;i++)
{
  cin>>a[i];
}
charu();
for(int i=0;i<n;i++)
{
  cout<<a[i]<<" ";
}

  return 0;
}

实现插入排序

题目描述

实现插入排序算法。介绍如下：

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从前向后扫描，找到相应位置并插入。

请编写代码，完成 插入排序，对给定数据进行升序排列。

输入描述

第一行，数字 N (2≤N≤100)N (2≤N≤100),表示待排序的元素个数。

第二行，待排序的元素。

输出描述

输出一行，为升序序列。

输入输出样例

示例

输入

6
7 1 4 8 5 2

输出

1 2 4 5 7 8