首页 > 代码库 > 中位数
中位数
求给定整数数据中的第i小的数
如果数据量很大，不能一次读入内存，可以将数据分区间储存。具体而言，就是讲数据分为...-2^20~-1,0~2^20-1, 2^20~2*2^20-1,2*2^20~3*2^20-1....并统计每个区间有多少个数据。这样就可以判断第i小的数在哪个区间。并且可以判断它在该区间是第几小。
每个区间的大小是2^20,一共有2^32/2^20=2^12个区间，每个区间的数存放在一个文件中。2^20 * 4byte = 4MB,可以读入内存。
现在问题转化为了求4MB数据中的第j位数。
采用随机选取算法，最差时间复杂度为O(n^2),平均时间复杂度为O(n)
该算法的思路是，通过快速排序的分割方式，一次可以将数据分为两部分，主元最后的位置m就是一个m分割，前m个数小于主元，后面的数大于主元，主元是所有数中第m+1大的。如果m+1 = j，则问题就解决了。
如果m+1 < j，说明第j位数在第一次分割的后半部分，此时以m+1下标作为begin,以len-1作为end,继续分割。得到主元的位置s,则主元前面的s个数都小于主元，主元后面的数都大于主元，主元是所有数中的第s+1大。判断s+1和j的关系。
如果m+1>j，说明第j位数在第一次分割的前半部分，此时以下标0作为begin,以m-1作为end，继续分割。
最终可以得到j
注意，每次需要记录下begin和end。
/**求一组数据中的第i小的数*/#include<stdio.h>#include<stdlib.h>#include<time.h>int RandomPartition(int *A,int beg,int end){ int k = beg+rand()%(end-beg+1); int temp = A[beg]; A[beg] = A[k]; A[k] = temp; int s=A[beg]; int i=beg; int j=end; while(j>i) { while(A[j]>s && j>i) { j--; } if(j>i) { A[i]=A[j]; i++; } while(A[i]<s && i<j) { i++; } if(i<j) { A[j]=A[i]; j--; } } A[i] = s; return i;}int Median(int *A,int len,int i){ if(i>len || i<1) { printf("i>len\n"); exit(0); } else { int k; int beg =0; int end = len-1; k=RandomPartition(A,beg,end); while((k+1)!=i) { if((k+1)>i) { end = k-1; k=RandomPartition(A,beg,end); } else { beg = k+1; k=RandomPartition(A,beg,end); } } return A[k]; }}int main(){ int A[]={1,45,43,65,23,42,63,22,18,9}; srand((unsigned int)time(NULL)); printf("%d\n",Median(A,10,2)); return 0;}
中位数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。