现有 n 个正整数，要4.现有 n 个正整数，要求出这 n 个正整数中的第 k 个最小整数（相同大小的整数只计算一次）。（排序）求出这 n 个正整数中的第 k 个最小整数

要解决这个问题，你可以使用一种叫做“快速选择”（QuickSelect）的算法，它是快速排序的变种，专用于查找数组的第 k 小元素。这个算法通常比直接排序后再查找快得多，特别是当 n 很大而 k 接近中间值时。

下面是基本步骤：

1. **随机化**：首先从数组中随机选择一个元素作为枢轴（pivot），这样可以平均分布数据，减少最坏情况下的性能影响。

2. **分区操作**：将数组分为三部分：小于枢轴的、等于枢轴的和大于枢轴的。如果 k 落在小于枢轴的部分，那么我们需要在左侧子数组继续寻找；如果 k 等于枢轴的位置，则已经找到了目标；如果 k 在右侧，我们在右侧子数组中寻找。

3. **递归或迭代**：根据k和分区结果，选择相应的子数组，重复上述过程，直到找到第 k 个最小元素。

**Python 示例**:

import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]
    left = [x for x in arr[:pivot_index] if x < pivot]
    middle = [x for x in arr[pivot_index:] if x == pivot]
    right = [x for x in arr[pivot_index + 1:] if x > pivot]

    if k <= len(left):
        return quickselect(left, k)
    elif k < len(left) + len(middle):
        return arr[pivot_index]
    else:
        return quickselect(right, k - len(left) - len(middle))

# 使用示例
arr = [5, 2, 9, 1, 7, 6]
n = len(arr)
k = 3
result = quickselect(arr, k - 1)  # 函数索引从0开始，所以这里减1
print(f"第 {k} 个最小整数是：{result}")