对于给定的含有n元素的无序序列，求这个序列中第k（1≤k≤n）小的元素。pythond代码完整实现

可以使用快速选择算法来解决这个问题，其时间复杂度为O(n)。

具体思路是在快速排序的基础上进行改进，每次选择一个pivot，将序列分为左右两个子序列，如果pivot的位置正好是第k个元素，直接返回pivot的值；如果pivot的位置小于k，说明第k小的元素在右子序列中，递归寻找右子序列中的第k-pivot位置的元素；如果pivot的位置大于k，说明第k小的元素在左子序列中，递归寻找左子序列中的第k个元素。

以下是完整的Python代码实现：

def partition(arr, left, right):
    pivot = arr[left] # 以第一个元素为pivot
    i, j = left+1, right
    while i <= j:
        while i <= j and arr[i] < pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
    arr[left], arr[j] = arr[j], arr[left] # pivot放到正确的位置
    return j

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

def find_kth_smallest(arr, k):
    if k > len(arr) or k < 1:
        return None
    return quick_select(arr, 0, len(arr)-1, k)

# example usage
arr = [3, 1, 4, 2, 5]
k = 3
print(find_kth_smallest(arr, k)) # output: 3