编写程序，对给定的无序列表ls=［9,2,2,1,1,5,6,9,6,3］，输入一个数字k，输出无序列表中第k大的元素

可以使用快速选择算法来解决这个问题。快速选择算法是快速排序算法的变体，其思想是找到一个枢轴元素，将列表分成两部分，使得左边的元素都小于枢轴元素，右边的元素都大于枢轴元素。然后根据枢轴元素在列表中的位置来决定继续查找左半部分还是右半部分，直到找到第k大的元素为止。

下面是使用 Python 实现快速选择算法的代码：

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

ls = [9, 2, 2, 1, 1, 5, 6, 9, 6, 3]
k = 4
result = quick_select(ls, len(ls) - k + 1)
print(result)  # 输出第k大的元素

在上面的代码中，我们首先选择列表的第一个元素作为枢轴元素，然后将列表分成小于枢轴元素的左半部分和大于枢轴元素的右半部分。如果第k大的元素在右半部分，就继续查找右半部分，否则就继续查找左半部分。最终，如果找到的元素在右半部分，就返回右半部分的第k个元素，如果找到的元素在左半部分，就返回左半部分中第(k-右半部分长度-1)个元素。