用python写对于给定的含有n元素的无序序列，求这个序列中第k（1≤k≤n）小的元素。(时间复杂度要求为O(n))

解法一：快速选择算法

快速选择算法类似于快速排序算法，但是只需要对需要查找的一部分进行排序。具体步骤如下：

1. 选取一个枢轴元素 pivot，可以选择序列中的任意一个元素。

2. 将序列中所有小于 pivot 的元素放在 pivot 的左边，将所有大于等于 pivot 的元素放在 pivot 的右边。

3. 判断 pivot 的位置与 k 的大小关系，如果 pivot 的位置等于 k，直接返回 pivot；如果 pivot 的位置小于 k，则在 pivot 的右边再次进行快速选择；如果 pivot 的位置大于 k，则在 pivot 的左边再次进行快速选择。

4. 重复以上步骤，直到找到第 k 小的元素。

代码如下：

def quick_select(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = arr[0]
    left = [x for x in arr if x < pivot]
    right = [x for x in arr if x >= pivot]
    if len(left) == k-1:
        return pivot
    elif len(left) < k-1:
        return quick_select(right, k-len(left)-1)
    else:
        return quick_select(left, k)

解法二：线性时间选择算法

线性时间选择算法是一种比快速选择算法更加高效的算法，时间复杂度为 O(n)。具体思路如下：

1. 将序列分为 n/5 个组，每个组内部进行排序，选择每个组的中位数。

2. 对于第一步中找到的 n/5 个中位数，递归地进行线性时间选择，找到其中位数 x。

3. 以 x 为枢轴，将序列分为左右两部分，计算左半部分的元素个数 t。如果 t=k，则返回 x；如果 t<k，则在右半部分中递归地进行线性时间选择，找到第 k-t 小的元素；如果 t>k，则在左半部分中递归地进行线性时间选择，找到第 k 小的元素。

代码如下：

def linear_select(arr, k):
    if len(arr) <= 5:
        arr.sort()
        return arr[k-1]
    medians = [arr[i:i+5] for i in range(0, len(arr), 5)]
    medians = [sorted(median)[len(median)//2] for median in medians]
    x = linear_select(medians, len(medians)//2+1)
    left = [i for i in arr if i < x]
    right = [i for i in arr if i > x]
    t = len(left)
    if k == t+1:
        return x
    elif k < t+1:
        return linear_select(left, k)
    else:
        return linear_select(right, k-t-1)