用三个数组储存数值，原顺序，大小顺序

解题思路:

有三个数组，p,b,a。p为从小到大元素数值排序，并且起到储存元素数值的作用。

a为p对应到原位置的顺序，从0开始，注意a也是按某种意义的从小到大排序，与p不同的是，它存的是原位置不是数值。

b为原顺序的大小顺序，但是是从0开始。b承担了许多作用，它是唯一按原顺序储存的，而a和p是按大小排序的，所以想按原顺序的排序方式输出时就要用b。

实际上，b和a 是相互储存对方的位置（a为从小到大对应到原位置的顺序，b为原顺序的大小顺序）。也就有了这步 b[i]=x,a[x]=i;

很好玩的是 a[b[i]]就是原顺序的第i个的原位置，也就是等于i 。

b[a[i]]就是从小到大的第i个的原位置的大小排序位置，也就还是等于i 。（很绕是吗，没错，我自己都快整不明白了）

由于p为从小到大元素数值排序，所以p[b[i]]进行循环输出就可以输出未进行排序的原元素数值。

在循环过程中，因为 a和p是大小顺序进行储存，所以经常要整个移动。而b是按原插入顺序存储，所以位置并不变，只改变数值，即储存的大小顺序。

循环过程：每次插入一个新元素时，从大到小进行大小比较，直达找到位置。
具体表现为新元素数值 c<p[x] 时，即要往左移，所以p[x]和a[x]的位置都要往右移一格，表现为p[x+1]=p[x]和a[x+1]=a[x]。（但是a的这一步要慢一步执行）

同时p[x]的大小顺序要加一，而a并非大小顺序，要往外再套一层b才是p[x]的大小顺序，具体表现为b[a[i]]加一。

经过这两行就成功将p[x]往右一格。

然后就可以重复直到找到位置，赋值后就可以开启下一步循环。

(其实应该可以用二路并归排序的，但我还没构思好，没想到用插入排序就过了，居然才测试了两个例子)；

注意事项:

由于我们代码的大小顺序从0开始，所以输出时要加一。

由于涉及到+1，因此0号位也就是初始赋值要循环外。

大小比较时要防止下溢。
参考代码:

# include<stdio.h>
int main(){ 
        int n;
	int *p;
	int *b;
	int *a;
	while(scanf("%d",&n)!=EOF){
    p=(int *)malloc(n*sizeof(int));
    b=(int *)malloc(n*sizeof(int));
    a=(int *)malloc(n*sizeof(int));
    scanf("%d",&p[0]);b[0]=a[0]=0;  //防止p[x+1]上溢
    for(int i=1,c,x;i<n;i++){
    	scanf("%d",&c);  //数值存给c
		x=i-1;  //循环起始点为i-1，表现为与已排序的最大值进行比较
    	while(x>=0){   //x小于0时就是c是最小值
		if(c<p[x])b[a[x]]++,p[x+1]=p[x],a[x+1]=a[x];  //上面十几行文字解释的这步操作
    	else break;
    	x--;  //继续与下一位比较大小
		}
		x++;  //由于每次循环最后都是x--，x是指向指定位置的左一位，因此要+1调整到正确位置,此时x就是大小排序了
    	p[x]=c,b[i]=x,a[x]=i;  //将数值c赋值给p[x],将大小排序x赋值给b[i]，将原位置i赋值a[x]
	}
	for(int i=0;i<n-1;i++)printf("%d ",b[i]+1);
	printf("%d\n",b[n-1]+1);//最后不能有空格
	free(p);
	free(b);
	free(a);
	}
	return 0;
}