digui.rar_分治法中位数

// 分治递归.cpp : 定义控制台应用程序的入口点。 // #include"stdafx.h" #include<iostream> #include<stdlib.h> #include<time.h> using namespace std; #define MAX_VALUE 100 #define random() rand()%MAX_VALUE #define N 10 #define MIDDLE 5 int a[N]; class Find { public: void bubble(int first,int end) //冒泡排序 { for(int i = first; i < end; i++) for(int j = end; j > i; j--) if(a[j]<a[j-1]) { swap(a[j], a[j - 1]); } } int partition(int p,int r,int x) //数组a中从a[p]到a[r]的元素按照x划分,大于x的在左边,小于x的在右边 { int i = p - 1, j = r + 1; while (1) { while (a[++i] < x && i < r); while (a[--j] > x); if (i >= j) break; swap(a[i], a[j]); } return j - 1; } int select(int p,int r,int k) //寻找中位数 { if(r - p < 75) { bubble(p,r); return a[p+k-1]; } for(int i = 0; i < (r - p - 4) / 5; i++) { int s = p + 5 * i, t = s + 4; bubble(s,t); int temp = a[p + i]; a[p + i] = a[s + 2]; a[s + 2] = temp; } // 找中位数的中位数 int x = select(p, p + (r - p - 4) / 5, (r - p - 4) / 10); int i = partition(p, r, x); int j = i - p + 1; if(k <= j) return select(p, i, k); else return select(i + 1, r, k - j); } }; int main() { cout<<"请输入十个数："<<endl; srand((int)time(NULL)); for(int k = 0; k < N; k++) { cin>>a[k]; } for(int k = 0; k < N; k++) { cout <<"a["<<k<<"]=" <<a[k] << "\t"; } cout << endl; Find f; int n=MIDDLE; cout << "中位数为 :" << f.select(0, N-1, n) << endl; return 0; }