羊瑞大佬说:“现在的年轻人啊,写个快排都能写错,比如那个辣鸡的ModricWang”
ModricWang觉得他说的情况是真的,决定帮自己复习一下快排的写法。
快排的一个基础操作就是划分$(partition)$ ,就是将当前的数组分为前后两个部分。
一种较为经典的$partition$ 方法是,将数组中处于中间位置(注意,只和位置有关,和大小无关)的元素作为分隔元素,然后将小于它的元素放到左侧,大于它的元素放到右侧,然后对左右两侧分别进行递归操作。在此题中为了统一,如果数组长度为偶数,取靠后的一个作为分隔元素。
需要注意的是,快排的划分是一种原地划分,而且左右两边的长度是未知的,因此它在操作时采取以下的一种方式:
进行第一次递归时,数组被分为左右两个部分:$[0, i)和[i,n),其中i就是执行partition时的i$。进行第二层的递归时,数组总共被分为4个部分。现在ModricWang想让你输出第二层递归时从左往右的第二部分的元素。
第一个数为数组长度$n$ ,$16 \leq n \leq 10^6$
第二行n个整数,为待排序的元素,保证在int范围内且不重复
输出一行,第二层递归时从左往右的第二部分的元素。
数据保证这一部分不为空。
16
10 6 2 7 14 4 1 13 8 15 5 3 9 11 12 16
7 6 8
原数据
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