线性时间选择算法

线性时间选择算法

 

找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，中位数处于1/2*[n/5-1]，即n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。

这个其实比较容易理解：

数组中共n个元素，5个元素一组，一共分成约m=n/5组。每组中间大小的那个数不妨称其为“次中位数”。

在m=n/5个“次中位数”中再取出中间值，这就是整个数组的“中位数”X。

很显然，约有一半的“次中位数”比X还要小【(n-5)/10<m/2】

在这些组中，每组起码要有3个元素（连“次中位数”也算上）比X小，

所以整个数组中起码要有3(n-5)/10个元素比X小。

当n≥75时3(n-5)/10≥n/4，也就是说起码有1/4的元素比X小。

同理，起码也有1/4的元素比X还要大。

这样就保证了这个中位数的选择比较合理，划分之后最长的数组也不会超过原来的3/4，总体划分比较均匀

假设你们年级有10个班，每个班只有5个人。

某次考试中，你在你们班考了第三名(次中位数)。

将每个班的第三名放在一起比较，你在这十个人中排第5名(中位数)。

那岂不是说，整个年级中至少有15个人成绩比你还要低？