sponsored links

The median

快速查找中位数(期望O(N)的算法)

November 30
快速查找中位数(期望O(N)的算法)
类似于快速排序那种,只不过另加处理一番. 附上代码: #include<bits/stdc++.h> using namespace std; const int maxn=1e2+5; int n,a[maxn]; double select_middle(int beg,int end) { if(n==1)return a[0]; int i=beg; for(int j=i+1;j<=end;j++){ if(a[j]<a[beg]){ ++i; swap(a[i],a[j