给定一个长度为 n的整数数列，以及一个整数 k，请求出数列从小到大排序后的第 k个数。 输入格式: 第一行包含两个整数 n（1≤n≤100000） 和 k（1≤k≤n）。 第二行包含 n个整数（所

这个问题描述的是求解数组的第 k 小元素（也称为“快速选择”或“Kth smallest element”），它通常通过分治算法来解决。你可以使用一种类似于快速排序的思想，但是只需要找到第 k 个小元素，所以不需要完全排序整个数组。以下是基本步骤：

1. 首先随机选择一个基准值（pivot）。
2. 将数组分为两部分，一部分是所有小于基准值的元素，另一部分是所有大于等于基准值的元素。
3. 如果基准值的位置正好是 k-1（其中 k 表示目标位置），那么找到了第 k 小的元素；如果基准值的位置大于 k-1，说明第 k 小的元素在左半部分数组中，应在左半部分继续查找；反之，如果小于 k-1，则在右半部分继续查找。
4. 对于每一步的选择，递归地应用此过程，直到找到目标位置的元素。

Python伪代码如下：

def quickselect(nums, k):
    if len(nums) == 1:
        return nums[0]
    
    pivot_index = random.randint(0, len(nums)-1)
    pivot_value = nums[pivot_index]
    nums[pivot_index], nums[-1] = nums[-1], nums[pivot_index]  # 将最后一个元素放在最后作为新的基准
    
    partition_size = 0
    for i in range(len(nums) - 1):
        if nums[i] < pivot_value:
            partition_size += 1

    if k == partition_size:
        return nums[-1]  # 已经找到第 k 小的元素
    elif k < partition_size:
        return quickselect(nums[:partition_size], k)
    else:
        return quickselect(nums[partition_size + 1:], k - partition_size - 1)

# 示例
nums = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
k = 3
result = quickselect(nums, k)