题目描述
羊瑞大佬说："现在的年轻人啊，写个快排都能写错，比如那个辣鸡的ModricWang"觉得他说的情况是真的，决定帮自己复习一下快排的写法。
快排的一个基础操作就是划分(partition)，就是将当前的数组分为前后两个部分。
一种较为经典的partition方法是，将数组中处于中间位置（注意，只和位置有关，和大小无关）的元素作为分隔元素，然后将小于它的元素放到左侧，大于它的元素放到右侧，然后对左右两侧分别进行递归操作。在此题中为了统一，如果数组长度为偶数，取靠后的一个作为分隔元素。
需要注意的是，快排的划分是一种原地划分，而且左右两边的长度是未知的，因此它在操作时采取以下的一种方式：
- 设数组为arr[n]，元素从0开始存储
- 令i=0，j=n−1,mid=arr[n/2]
- 如果i≤j，转到4，否则转到步骤7
- 如果arr[i]<mid，重复执行直到arr[i]≥mid
- 如果arr[j]>mid，重复执行直到arr[j]≤mid
- 如果i≤j，交换arr[i]和arr[j]，i++,j−−，转到步骤4
- 退出
进行第一次递归时，数组被分为左右两个部分：[0,i)和[i,n)，其中i就是执行partition时的i[0,i)和[i,n)，其中i就是执行partition时的i 。进行第二层的递归时，数组总共被分为4个部分。现在ModricWang想让你输出第二层递归时从左往右的第二部分的元素。
输入
第一个数为数组长度n,16≤n≤106
第二行n个整数，为待排序的元素，保证在int范围内且不重复
输出
输出一行，第二层递归时从左往右的第二部分的元素。
数据保证这一部分不为空。
输入样例
16
10 6 2 7 14 4 1 13 8 15 5 3 9 11 12 16
输出样例
7 6 8
HINT
原数据
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
思路
无
参考代码
1 #include<stdio.h> 2 #define MAXN 1000002 3 int arr[MAXN]; 4 int main() 5 { 6 int n; 7 scanf("%d",&n); 8 int i; 9 for(i = 0;i < n;i++) 10 scanf("%d",&arr[i]); 11 quicksort(0,n-1,1); 12 } 13 14 void quicksort(int l,int r,int depth) 15 { 16 int i = l,j = r,mid = arr[(i+j+1)/2]; 17 while(i <= j){ 18 while(arr[i] < mid) 19 i++; 20 while(arr[j] > mid) 21 j--; 22 if(i <= j){ 23 swap(&arr[i],&arr[j]); 24 i++;j--; 25 } 26 } 27 if(depth == 2){ 28 for(;i <= r;i++) 29 printf("%d ",arr[i]); 30 printf(" "); 31 exit(0); 32 } 33 if(l < j) 34 quicksort(l,j,depth+1); 35 if(r > i) 36 quicksort(i,r,depth+1); 37 } 38 39 void swap(int *a,int *b) 40 { 41 int tmp; 42 tmp = *a; 43 *a = *b; 44 *b = tmp; 45 }