求数列中的第1～k小元素

求数列中的第1～k小元素
1.问题描述设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题，这里k不是常量，即它是输入数据的一部分。
要求算法的时间复杂性为Θ(n)。
2.具体要求输入的第一行是一个正整数m，表示测试例个数。
接下来几行是m个测试例的数据，每个测试例的数据由三行组成，其中其中，第一行输入一个正整数n，表示元素的个数；
第二行输入n个整数，整数之间用一个空格隔开。
第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。
（设给出的每个整数序列中的元素是独一的。
）输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。
整数之间用一个空格隔开。
两个测试例的输出数据之间用一个空行隔开。
3.测试数据输入：21956342271695463781127326193168423725182683328175157493511253714321352126232545162223713输出：3712161922263123567811121314161722 本软件ID:2273450