解答：

K-SMALLEST-ELEMENTS(A, n, k)
    for i = 1 to k
        min_id = i
        for j = i to n
            if A[j] < A[min_id]
                min_id = j;
        exchange A[min_id] with A[i]
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，需要遍历 10 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

评分：5分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。

当然这里可以进行优化，每次记录两个变量，找出最小值和次小值，这样只需要遍历 k/2 次数组。

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(1) ，中间过程额外需要常数个变量。

评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度不是最优，但是可以进行大幅优化。

进一步优化，直接记录 k 个变量，或者一个长度为 k 的辅助数组，使用插入排序或者冒泡排序的方法，找出最小的 k 个数，这样只需要遍历 1 次数组。

• 时间复杂度： O(nk) ，需要遍历 k 次数组。
• 空间复杂度： O(n) ，中间过程额外需要大小为 k 的辅助数组。

评分：6分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，都可以进行大幅优化。

以上这些优化手段都无法降低时间复杂度。

伪代码如下：

MAX-HEAPIFY(A, i, n)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ n and A[l] > A[i]
        largest = l
    else largest = i
    if r ≤ n and A[r] > A[largest]
        largest = r
    if largest ≠ i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

BUILD-MAX-HEAP(A, n)
    for i = ⌊n / 2⌋ down to 1  // 也可用floor函数表示向下取整
        MAX-HEAPIFY(A, i, n)

K-SMALLEST-ELEMENTS(A, n, k)
    BUILD-MAX-HEAP(A, k)
    for i = k + 1 to n
        if A[i] < A[1]
            A[1] = A[i]
            MAX-HEAPIFY(A, 1, k)
    return A[1 : 10]
// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，由于堆大小为常量，所以建堆，维护堆的代价为 O(1) ，仅需要遍历一遍数组，该算法时间复杂度为 O(n) 。
• 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(nlog⁡k) ，所以建堆的代价为 O(k) ，每次维护堆的代价为 O(log⁡k) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlog⁡k) 。
• 空间复杂度： O(1) ，该算法原地建堆，使用了常数个辅助变量，该算法的空间复杂度为 O(1) 。

评分：9分，虽然当 k 为常数时时间复杂度为最优，实际上时间复杂度不是最优，可以继续进行优化。

当然，这里也可以使用优先队列，本质思想是一致的。

如果使用二叉堆作为优先队列，为插入建堆，明显不如直接用堆好。

• 时间复杂度： O(nlog⁡k) ，插入建堆的代价为 O(klog⁡k) ，每次维护堆的代价为 O(log⁡k) ，仅需要遍历一遍数组，总共 n 个元素，该算法时间复杂度为 O(nlog⁡k) 。
• 空间复杂度： O(k) ，该算法用了大小为 k 的堆的辅助数组，该算法的空间复杂度为 O(k) 。

用二叉堆作为优先队列并不能对时间复杂度进行优化。

评分：8分，虽然当 k 为常数时时间复杂度和空间复杂度表面上均为最优，实际上时间复杂度和空间复杂度都不是最优，可以继续进行优化。

当然可以使用更高级的数据结构实现优先队列，比如用Emde Boas树实现，时间复杂度降为 O(nlog⁡log⁡k) ，但是仍然可以继续进行优化。

方法三：选择算法（快速排序思想）

题目已经给出重要提示：“平均情况下的比较次数尽可能少”，明显指向随机化选择算法。也是本题的最优解。

为什么给出这个结论呢？“平均情况下”意思是不需要考虑最坏情况，哪些算法最坏情况下的时间复杂度和平均情况下的时间复杂度有区别呢？我们很容易想到快速排序，那么快速排序是如何进行优化的呢？其中一个最常规的方法就是随机化，当然同理，如果学过《算法导论》的同学马上能联想到选择算法。还有一个条件就是“比较次数尽可能少”，这个什么意思呢？绝大部分排序算法都是基于比较的排序算法，其中性能最好的就是快速排序，这道题没有要求我们对所有数进行排序，所以没必要使用平均情况下时间复杂度为 O(nlog⁡n) 的随机化快速排序算法，只需要使用平均情况下时间复杂度为 O(n) 的随机化选择算法算法。两者思路非常相近，都使用了随机化和划分数组技巧。

牢记：408题目中每一个条件都是有用的！

其实选择算法在2016年第43题已经进行过考察，也就是吃透真题非常重要，往年考过的知识点很有可能再考。

虽然RANDOMIZED-SELECT和RANDOMIZED-QUICKSORT代码非常相似，但这方法绝对不是能在没有学习过RANDOMIZED-SELECT算法的情况下在考场上随机应变能想出来的，如果你做到了，完全可以说是天才。408非常强调平时积累的。

递归版伪代码如下：

PARTITION(A, p, r)
    x = A[r] // the pivot
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1  // new index of pivot

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-SELECT(A, p, r, i)
    if p == r
        return A[p] // 1 ≤ i ≤ r - p + 1 when p == r means that i = 1
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q - p + 1
    if i == k
        return A[q] // the pivot value is the answer
    else if i < k
        return RANDOMIZED-SELECT(A, p, q - 1, i)
    else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

K-SMALLEST-ELEMENTS(A, n, k)
    RANDOMIZED-SELECT(A, 1, n, k)
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
• 空间复杂度： O(log⁡n) ，平均情况下递归栈深度为 O(log⁡n) 。

迭代版伪代码如下：

PARTITION(A, p, r)
    x = A[r] // the pivot
    i = p - 1
    for j = p to r - 1
        if A[j] ≤ x
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1  // new index of pivot

RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    exchange A[i] with A[r]
    return PARTITION(A, p, r)

RANDOMIZED-SELECT(A, n, i)
    p = 1
    r = n
    q = 0
    k = 0
    while TRUE 
        q = RANDOMIZED-PARTITION(A, p, r);
        k = q - p + 1;
        if i == k 
            return A[q]  // the pivot value is the answer
        elseif i < k
            r = q - 1
        else p = q + 1
            i = i - k

K-SMALLEST-ELEMENTS(A, n, k)
    RANDOMIZED-SELECT(A, n, k)
    return A[1 : k]

// Call function
K-SMALLEST-ELEMENTS(A, n, 10)

复杂度分析：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 10 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 10 的元素即为最小的 10 个数，时间复杂度 O(n) 。
• 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。

如果这里将 10 修改为 k ，则：

• 时间复杂度： O(n) ，用RANDOMIZED-SELECT选出第 k 小的数，而且已经用这个数作为枢轴对数组进行划分，下标前 k 的元素即为最小的 k 个数，时间复杂度 O(n) 。
• 空间复杂度： O(1) ，由于RANDOMIZED-SELECT和PARTITION都是原地算法，该算法的空间复杂度为 O(1) 。

可以发现，此算法时间复杂度和空间复杂度不受参数 k 影响，性能非常优秀。

评分：10分，时间复杂度和空间复杂度均为最优。

总结

本题本质就是Top-K问题，对排序算法思想进行了深入考察，Top-K问题非常经典，并不要求最终数组完全有序，只需要部分有序或者部分相对有序，所以充分利用排序算法的性质就能实现。