已知有兩個等長的非降序序列S1, S2, 設計函數求S1與S2并集的中位數。有序序列A
0
,A
1
,⋯,A
N−1
的中位數指A
(N−1)/2
的值,即第⌊(N+1)/2⌋個數（A
0
為第1個數）。
輸入格式:
輸入分三行。第一行給出序列的公共長度N（0<N≤100000），随後每行輸入一個序列的資訊，即N個非降序排列的整數。數字用空格間隔。
輸出格式:
在一行中輸出兩個輸入序列的并集序列的中位數。
輸入樣例1:
5
1 3 5 7 9
2 3 4 5 6
輸出樣例1:
4
輸入樣例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
輸出樣例2:
1
運用快速排序，将數組中的元素從小到大排列，然後找到題目要求的那個數即可。
代碼如下：
#include<stdio.h>
#include<stdlib.h>
int a[1000005];//這裡要多開一個數量級，題目給的數大
void quick_sort(int l,int r)
{
if(l<r)//即Swap(s[l],s[(l + r)/2]);//将中間的這個數和第一個數交換
{
int i=l,j=r,x=a[l];
while (i<j)
{
while(i<j&&a[j]>=x)//從右向左找第一個小于x的數
j--;
if(i<j)
a[i++]=a[j];
while(i<j&&a[i]<x)//從左向右找第一個大于等于x的數
i++;
if(i<j)
a[j--]=a[i];
}
a[i]=x;
quick_sort(l,i-1);//遞歸調用
quick_sort(i+1,r);
}
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n*2;i++)
{
scanf("%d",&a[i]);
}
quick_sort(1,n*2);
printf("%d",(a[n]));
}