---

(1)即保证A1与A2个数尽可能相同，且A2尽可能大，A1尽可能小，故让后方序列中均为较大的数，前方序列为较小的数，为保证个数相同，借助快速排序中的分治思想，通过寻找中间元素的位置，将原数组拆分成两个序列，仅需进行一次分治处理,此时前后序列即为所求。

（2)

初始化数组a[n];

int mid=n/2;//中间元素作为基准

int low=0;int high=n-1;

int partion(int a[];int low;int high)//执行划分操作

{

while(low<high)

{

int pivot=a[low];

while(low<high&&a[high}>=pivot)high--;

a[low]=a[high];

while(low<high&&a[low]<=pivot)high++;

a[high]=a[low];

}

a[low]=pivot;

return low;

}

int QuickSelect(int a[n],int low,int high)

{

int judge=partion(a[n],low,high);

if(judge=mid) return 0;//找到mid时，说明数组中间元素以成功找到，此时序列划分完毕，停止划分

else

{

QuickSelect(a[n],low,judge-1);

QuickSelect(a[n],judge+1,high);

}

}

(3)时间复杂度为o(nlogn),空间复杂度为o(n)

---