求n个元素第k小的元素
1)在五个一组时，我们知道中位数的中位数是数组中第n/2小的元素，其中n为数组的长度。现在我们想要找到比中位数的中位数x小或大的数，我们可以将数组分为五个一组，每组中找出中位数，并将这些中位数组成新的数组，然后再找出这个新数组的中位数y。
如果x比y小，我们可以把原数组中所有小于等于y的数放到左边，所有大于y的数放到右边，然后递归地在左边找第k小的数，或者在右边找第k-L(n-5)/10小的数。如果x比y大，则递归地在右边找第k小的数，或者在左边找第k+L(n-5)/10小的数。
为什么L(n-5)/10是比中位数的中位数x小或大的数的个数呢？因为我们可以把所有小于等于y的数放到左边，所有大于y的数放到右边，那么就有3n/10个数比y小或相等，还有3n/10个数比y大或相等，因为y是中位数的中位数，所以数组中小于等于y的数和大于等于y的数的个数相等，所以比y小或大的数的个数就是3n/10的一半，即L(n-5)/10。
时间复杂度是O(n)，因为每次递归只需处理3/10的元素。
2)7个一组时，我们可以将数组分为7个一组，每组中找出中位数，并将这些中位数组成新的数组，然后再找出这个新数组的中位数y。与5个一组时类似，我们可以将原数组中所有小于等于y的数放到左边，所有大于y的数放到右边，然后递归地在左边找第k小的数，或者在右边找第k-4n/7小的数。
每次递归只需处理4/7的元素，时间复杂度为O(n)。
3)3个一组时，我们可以将数组分为3个一组，每组中找出中位数，并将这些中位数组成新的数组，然后再找出这个新数组的中位数y。但是，此时如果将原数组中所有小于等于y的数放到左边，所有大于y的数放到右边，就不能保证左边的元素个数小于k，右边的元素个数小于n-k。
因此，3个一组的方法不能用来求第k小的元素，时间复杂度也无法估算。
首先，对于求解n个元素第k小的元素的问题，一般可以采用快速选择算法，时间复杂度为O(n)。
接下来，我们来解释为什么在五个一组时，比中位数的中位数x大或者小的数是3*└（n-5）/10┘。
假设我们有n个元素，将它们分成五个一组，一共有└n/5┘组。对于每一组，我们可以通过插入排序的方式将五个元素排序，然后取出其中位数，然后将这些中位数也按照大小排序，最终得到中位数的中位数x。
现在我们来考虑比x小的元素个数。由于x是中位数的中位数，那么在排序后的序列中，比x小的元素个数一定不超过└n/2┘。又因为每组取出一个中位数，所以在这些中位数中，比x小的元素个数至少为└└n/10┘/2┘=└n/20┘，即我们可以在n个元素中找到至少└n/20┘个比x小的元素。
而当我们取出比x小的元素时，每组可以取出三个元素（因为前面已经取出了中位数），因此我们可以在剩下的n-5（除去中位数的中位数和中位数）个元素中，每五个元素一组，取出每组中最小的一个元素，从而得到至少└n/20┘个比x小的元素，即3*└（n-5）/10┘。
同理，我们可以得到比x大的元素个数为3*└（n-5）/10┘。
因此，在五个一组时，比中位数的中位数x小或大的元素的个数为3*└（n-5）/10┘。时间复杂度为O(n)。
接下来我们考虑7个一组的情况。同样地，我们可以将n个元素分成7个一组，一共有└n/7┘组。对于每一组，我们可以通过插入排序的方式将7个元素排序，然后取出第4个元素。
类似地，我们可以找到比所有第4个元素小的元素个数，也可以找到比所有第4个元素大的元素个数。但是，在这种情况下，比第4个元素小或大的元素的个数并不容易直接计算，因此在7个一组时，我们采用了一种不同的方法。
我们首先对所有元素进行插入排序，然后取出第n/2小的元素，记为m。接下来，我们将所有小于m的元素放在左边，所有大于m的元素放在右边。则m的位置就是整个序列中第n/2小的元素。如果我们将序列分成长度为k和n-k两部分，它们分别包含了前k小和后n-k小的元素。
现在我们来考虑第k小的元素。如果k ≤ n/2，则我们只需要在长度为k的左半部分中递归地找第k小的元素即可。如果k > n/2，则我们只需要在长度为n-k的右半部分中递归地找第n-k-(k-n/2)小的元素。
可以发现，在以上的过程中，每个元素都会被比较一次，因此时间复杂度为O(n)。
最后，我们来考虑3个一组的情况。同样地，我们可以将n个元素分成3个一组，一共有└n/3┘组。对于每一组，我们可以通过插入排序的方式将3个元素排序，然后取出中间的一个元素。但是，这种方法无法直接推导出比中位数的中位数小或大的元素个数，因此不适用于快速选择算法。
综上所述，快速选择算法的时间复杂度为O(n)，并且在采用五个一组或者七个一组的方法时，可以直接推导出比中位数的中位数小或大的元素个数。
如果帮到你了望采纳