长度为n的整数序列，设计一个算法，返回序列第K小的元素

设计一个算法找到长度为 \( n \) 的整数序列中的第 \( K \) 小元素，可以采用一种高效的排序算法，如快速选择（QuickSelect），这是一种改进版的快速排序，其时间复杂度在平均情况下是线性的，即 \( O(n) \)，最坏情况下是 \( O(n^2) \) 但概率较低。

以下是快速选择的基本步骤：

1. **选择基准**（pivot）：从序列中随机选取一个元素作为基准。
2. **分区**（Partitioning）：将序列分为两部分，一部分所有元素小于基准，另一部分所有元素大于等于基准，基准元素在其最终位置上。
3. **比较**（Comparison）：如果基准的位置正好是 \( K-1 \)，则找到了第 \( K \) 小的元素；否则，根据基准的新位置调整目标范围。
- 如果基准位于右侧，说明第 \( K \) 小的元素应该在左半部分，所以在左半部分递归查找第 \( K \) 小的元素。
- 如果基准位于左侧，说明第 \( K \) 小的元素应该在右半部分，所以在右半部分递归查找第 \( (K-基准位置) \) 小的元素。
4. **递归终止**：当基准位置就是 \( K \) 或者 \( K+1 \) 时，查找结束，因为序列已经足够小，可以直接得到结果。

以下是一个伪代码版本：

function quick_select(arr, k):
    if len(arr) == 1:
        return arr[0]

    pivot_index = partition(arr)
    if k == pivot_index:
        return arr[k]
    elif k < pivot_index:
        return quick_select(arr[:pivot_index], k)
    else:
        return quick_select(arr[pivot_index+1:], k - pivot_index - 1)

def partition(arr):
    # ... 实现枢轴元素划分代码 ...