给定一个长度为n（1≤n≤1,000,000）的无序正整数序列，以及另一个数k（1≤k≤1,000,000）（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。）写出程序

好的，以下是一个使用快速选择算法求解无序正整数序列中第k大的数的Python程序：

def quick_select(nums, k):
    pivot = nums[0]
    left = [x for x in nums if x < pivot]
    right = [x for x in nums if x > pivot]
    equal = [x for x in nums if x == pivot]

    if k <= len(right):
        return quick_select(right, k)
    elif (k - len(right)) <= len(equal):
        return pivot
    else:
        return quick_select(left, k - len(right) - len(equal))
    
# 示例用法
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 4
result = quick_select(nums, k)
print(f"The {k}th largest number is {result}")

该程序中，首先选择列表中的一个数作为基准数，然后将列表分为三部分：比基准数小的部分、比基准数大的部分和等于基准数的部分。然后通过比较k和右半部分的长度和等于部分的长度，确定需要在哪一部分中继续查找第k大的数。最后使用递归方式不断缩小查找范围，直到找到第k大的数。

注意，由于递归的过程中，每次都需要创建新的列表，因此该算法的空间复杂度为O(n)。实际上，在实际应用中，可以通过不断修改原始列表来减少空间开销。