E ModricWang's QuickSort
时间限制：1000ms 内存限制：65536kb
题目描述
羊瑞大佬说：“现在的年轻人啊，写个快排都吃力。”
ModricWang觉得他说的情况是真的，决定帮大家复习一下快排的写法。
快排的一个基础操作就是划分(partition)，就是将当前的数组分为前后两个部分。
一种较为经典的partition方法是，将数组中处于中间位置（注意，只和位置有关，和大小无关）的元素作为分隔元素，然后将小于等于它的元素放到左侧，大于它的元素放到右侧，然后对左右两侧分别进行递归操作。在此题中为了统一，如果数组长度为偶数，取靠后的一个作为分隔元素。
需要注意的是，快排的划分是一种原地划分，而且左右两边的长度是未知的，因此它在操作时采取以下的一种方式：
- 设数组为arr[n]，元素从0开始存储
- 令i=0，j=n-1, mid=arr[n/2]
- 如果 i < j，转到4，否则转到7
- 如果arr[i] <= mid, i++ ，重复执行直到arr[i]>mid
- 如果arr[j] > mid, j-- ，重复执行直到arr[j]<=mid
- 如果i < j, 交换arr[i]和arr[j]，转到4
- 退出
进行第一次递归时，数组被分为左右两个部分。进行第二层的递归时，数组总共被分为4个部分。现在ModricWang想让你输出第二层递归时从左往右的第二部分的元素。
输入
第一个数为数组长度n,16≤n≤10616≤n≤106
第二行n个整数，为待排序的元素，保证在int范围内且不重复
输出
输出一行，第二层递归时从左往右的第二部分的元素。
数据保证这一部分不为空。
输入样例
16
10 6 2 7 14 4 1 13 8 15 5 3 9 11 12 16输出样例
7 6 8HINT
原数据
10 6 2 7 14 4 1 13 8 15 5 3 9 11 12 16第一次递归
3 6 2 7 5 4 1 8 / 13 15 14 10 9 11 12 16第二次递归
3 1 2 4 5 / 7 6 8 / 9 / 15 14 10 13 11 12 16题目分析
本题解决的关键就是完全根据题中所述写出一个排序函数，将其运行两次，找出所要输出的值即可。
第一次递归完成时，i=j，这时数列被划分成了两部分，由于我们要找的是第二次递归完成时的第二部分，所以我们只要对前半部分再进行一次递归就好了。
将i重置为0，并记录此时前半部分的结束位置j，中间标志元素mid=num[(j+1)/2]，循环结束后，只要输出比mid大的数即可。
示例代码
#include<cstdio>
int a[1000007];
int exchange(int &a,int &b)
{int t=b;b=a;a=t;
}
int mysort(int num[],int l,int r)
{int i=l,j=r-1;int mid=num[(l+r+1)/2];while(i<j){while(num[i]<=mid)i++;while(num[j]>mid)j--;if(i<j)exchange(num[i],num[j]);}i=0;int oend=j;mid=num[(j+1)/2];while(i<j){while(num[i]<=mid)i++;while(num[j]>mid)j--;if(i<j)exchange(num[i],num[j]);}for(int k=0;k<=oend;k++){if(num[k]>mid){printf("%d ",num[k]);}}
}
int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}mysort(a,0,n);
}