c语言分治法对于给定的n个元素的数组a[1..n]，要求从中找出第k小的元素。 【输入样例】 a={20, 43, 32, 67 ,48, 89, 36, 47, 15} k=3 【输出样例】 32

题目分析

本题要求在一个无序数组中找到第 $k$ 小的元素，可以使用分治法（快速选择算法）来解决。快速选择算法的思想和快速排序类似，都是通过分治思想将问题规模不断缩小，最终找到解决方案。

具体而言，我们可以通过快速排序的思路来进行分治。在快速排序中，我们选择一个主元（pivot），将数组分为两部分，左边的元素小于等于主元，右边的元素大于主元，然后递归地对左右两部分进行排序。在快速选择算法中，我们同样选择一个主元，但是只需要对主元所在的一边进行排序，另一边则不需要再排序。具体实现时，我们可以先将数组分为两部分，左边的元素小于等于主元，右边的元素大于主元，然后根据主元的位置和 $k$ 的大小关系，递归地在左边或右边继续查找第 $k$ 小的元素。如果主元的位置恰好为 $k-1$，那么主元就是第 $k$ 小的元素；如果主元的位置小于 $k-1$，那么第 $k$ 小的元素一定在右边；如果主元的位置大于 $k-1$，那么第 $k$ 小的元素一定在左边。

时间复杂度：$O(n)$（期望情况下，最坏情况下为 $O(n^2)$）

代码实现