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