交叉排序

交叉排序

Time Limit: 1000MS Memory limit: 32768K

题目描述

输入N个数，把所有奇数位置上的数从小到大排序，把偶数位置上的数从大到小排序。

输入

输入的第一行是一个正整数N(2<=N<=100)。 第二行是N个用空格隔开的整数。

输出

输出只有一行N个数，是按要求排序后的序列，用空格隔开。

示例输入

6 1 2 3 4 5 6

示例输出

1 6 3 4 5 2

提示

 

来源

2011软件1-5班《程序设计基础》机试 tongjiantao

示例程序

#include<stdio.h> #include<string.h> #include<stdlib.h> #define num 1003 int a[num],b[num]; void qsort1(int a[],int l,int r) { int key = a[l],i = l,j = r; if(l >= r) return ; while(i < j) { while(i < j && a[j] >= key) j--; a[i] = a[j]; while(i < j && a[i] <= key) i++; a[j] = a[i]; } a[i] = key; qsort1(a,l,i-1); qsort1(a,i+1,r); } void qsort2(int a[],int l,int r) { int key = a[l],i = l,j = r; if(l >= r) return ; while(i < j) { while(i < j && a[j] <= key) j--; a[i] = a[j]; while(i < j && a[i] >= key) i++; a[j] = a[i]; } a[i] = key; qsort2(a,l,i-1); qsort2(a,i+1,r); } int main() { int n; int x; scanf("%d",&n); int j = 0,k = 0; for(int i = 1;i <= n;i++) { scanf("%d",&x); if(i % 2 != 0) a[j++] = x; else b[k++] = x; } qsort1(a,0,j-1); qsort2(b,0,k-1); j = 0,k = 0; for(int i = 1;i <= n;i++) { if(i == 1) printf("%d",a[j++]); else { if(i%2 != 0) { printf(" %d",a[j++]); } else { printf(" %d",b[k++]); } } } printf("\n"); return 0; }