1800 - 基础排序II：插入排序

10
10 9 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8 9 10

提示

	具体算法描述如下：


	⒈ 从第一个元素开始，该元素可以认为已经被排序


	⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描


	⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置


	⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置


	⒌ 将新元素插入到下一位置中


	

		⒍ 重复步骤2
	
	

		
</p>
<p>
	每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。
</p>

C语言解答

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int N;
    scanf("%d",&N);
    int i,j,a[N+1];
    for(i=1;i<N+1;i++)
    {
        scanf("%d",a+i);

    }


    for(i=2;i<N+1;++i)
    {
        if(a[i-1]>a[i])
        {
             a[0]=a[i];
             a[i]=a[i-1];
             for(j=i-2;a[0]<a[j];--j)
             {
                 a[j+1]=a[j];
             }
             a[j+1]=a[0];
        }

    }
    for(i=1;i<N+1;i++)
        printf("%d ",*(a+i));
    printf("\n");
    return 0;
}

C++解答

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
int a[100001],n,i;
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	for(i=1;i<=n;i++) printf("%d ",a[i]);
	cout<<endl;
	return 0;
}