基于选择排序查找指定排名元素及线性时间复杂度的技术问询

问题解答 #

首先明确前提：班级学生成绩为互不相同的整数，排名从高到低（排名1为最高分，排名n为最低分），且k为偶数（需恰好k/2名排名高于X、k/2名低于X）。题目中提到的「第(R-k)名和第(R+k)名」应为笔误，实际是第(R - k/2)名（高于X的k/2名的最边界）和第(R + k/2)名（低于X的k/2名的最边界），否则R+k可能超出n的范围，不符合题意。

1. 如何利用选择排序找到目标边界元素？

选择排序的核心是每次在未排序区间中找到最值，将其交换到已排序区间的末尾。我们不需要完全排序整个数组，只需要执行部分选择排序就能定位到目标排名的元素：

步骤详解：

• 确定目标排名：设上边界排名为 t1 = R - k/2（高于X的k/2名的最边界），下边界排名为 t2 = R + k/2（低于X的k/2名的最边界），确保 1 ≤ t1 < R < t2 ≤ n。
• 执行部分选择排序：
  1. 初始化未排序区间为整个数组（假设数组索引从0开始）。
  2. 重复t2次以下操作：
     • 在当前未排序区间中，遍历找到成绩最高的元素的索引。
     • 将该最高分元素与未排序区间的第一个元素交换位置（此时数组前i+1个元素就是前i+1名的成绩，i为当前循环次数）。
     • 缩小未排序区间为「当前起始索引+1」到数组末尾。
• 提取目标元素：循环结束后，数组的t1-1索引位置就是第t1名的成绩，t2-1索引位置就是第t2名的成绩。
• 筛选目标学生：数组中从t1-1到t2-1的元素就是排名在t1到t2之间的所有学生，去掉X自己的成绩，剩下的就是与X排名最接近的k名学生。

举个实际例子：假设n=10，X排名R=5，k=4（需要2名高于X、2名低于X），则t1=3，t2=7。执行7次选择排序循环后，数组索引2对应第3名，索引6对应第7名；数组索引2到6的元素是第3-7名，去掉X的第5名，剩下的第3、4、6、7名就是我们要找的4名学生。

2. 为何该算法的时间复杂度为线性？

完全选择排序的时间复杂度是O(n²)，但这里我们只执行了t2次循环，关键在于k是固定的常数（我们要找的是与X排名最接近的k名学生，k远小于n）。

我们来计算总操作次数：每次循环需要遍历当前未排序区间的元素，第1次遍历n个元素，第2次遍历n-1个，……，第t2次遍历n - t2 + 1个元素。总操作次数为：

S = n + (n-1) + (n-2) + ... + (n - t2 + 1) = t2*(2n - t2 + 1)/2

由于k是常数，t2 - t1 = k，也就是说我们只需要在找到t1名的基础上，多执行k次循环就能找到t2名元素，这部分额外操作次数约为k*n。当k是固定小值时，总操作次数S = O(n) + O(n) = O(n)，也就是线性时间复杂度。简单来说：我们不需要排序整个数组，只需要定位到与X排名接近的k个边界，k是固定值，所以总遍历次数与n成正比，属于线性复杂度。

内容的提问来源于stack exchange，提问作者ambakick