作业帮我有到求中位数的题,帮我解决如果在许多【比如100个等】大小不一的数中,怎么快速的求中位数,
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/28 08:07:35
我有到求中位数的题,帮我解决如果在许多【比如100个等】大小不一的数中,怎么快速的求中位数,
我有到求中位数的题,帮我解决
如果在许多【比如100个等】大小不一的数中,怎么快速的求中位数,
我有到求中位数的题,帮我解决如果在许多【比如100个等】大小不一的数中,怎么快速的求中位数,
把一组数据按从小到大的数序排列,在中间的一个数字（或两个数字的平均值）叫做这组数据的中位数.
中位数的算法：求中位数时,首先要先排序（从小到大）,然后计算中位数的序号,分数据为奇数个与偶数个两种来求.
中位数算出来可避免极端数据,代表着数据总体的中等情况.
如果总数个数是奇数的话,按从小到大的顺序,取中间的那个数
如果总数个数是偶数个的话,按从小到大的顺序,取中间那两个数的平均数
下面是我的回答，我贴了第三遍了（文字，学习他人）。
首先100个是极小规模的问题，可以用最差的选择排序O(n^2)，找到中间的数字就可以。
如果是十万左右的话可以采用快速排序，取得中间的数字。
另外如果你的数据量是一千万，就需要采用我下面的算法。
实数的排序算法复杂度是O(nlogn)，这个中位数可以做到O(n)
下面我来说明这个算法的过程。
算法是...
全部展开
下面是我的回答，我贴了第三遍了（文字，学习他人）。
首先100个是极小规模的问题，可以用最差的选择排序O(n^2)，找到中间的数字就可以。
如果是十万左右的话可以采用快速排序，取得中间的数字。
另外如果你的数据量是一千万，就需要采用我下面的算法。
实数的排序算法复杂度是O(nlogn)，这个中位数可以做到O(n)
下面我来说明这个算法的过程。
算法是基于归并排序（merge-sort）的更改。
把中位数更改为等价的叙述。无序的n个数中的第int(n/2)大的元素。(k=int(n/2))
1.随机化数据，这样可以保证因为输出时候的对称性（可能的顺序输入）而造成的算法退化。
for (int i=number.count;i>=0;i--)
swap(number[i],number[random(0,i-1)]);//swap，交换，random，0，k闭区间的随机数。
2.归并排序主过程。
mergesort(a,b,k)//寻找number数组中从下标a到下标b的元素中的第k大的元素。
{
t=number[a];
把这a,b中的元素从排，使a~p-1的元素比t小，p+1~b的元素比t大。number[p]=t;//O(n)，这步你构造吧。不是很困难，伪代码不写太多。
//此时比t小元素有p-1-a+1=p-a个,
//分情况，如果k=p-a+1,返回t
//如果k>p-a+1,返回mergesort(p+1,b,k-(p-a+1))
//如果k
以上算法T(n)=T(n/2)+O(n)
根据主定理，T(n)=O(n)。
收起
你画一个茎叶图，再数。