中位数定义:对于有限的数集,可以通过把所有元素高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。
实现思路
随机获取无序阵列中一个元素作为分割元素, 以分割元素为界限,将阵列分割大小阵列两部分。若“小”阵列的长度大于中位数索引值, 则基于“小”阵列继续选取随机值缩小其长度。舍弃比中位数值小的元素, 以减少计算量,相应的中位数索引左移对应长度, 保证相对原始资料索引长度不变。判断无序阵列中该分割元素个数, 若大于新的中位数索引, 则该分割元素就是中位数。若小于则舍弃分割元素, 因此调整中位数的索引值,左移对应长度。对“大""阵列重复上述计算。Python实现
测试结果
测试环境测试结果
同时,由于随机抽取元素,进行计算,算法表现稳定性不是很好。
算法复杂度
若对您有所帮助,欢迎大家评论、留言。