1.问题
在 数组S中查找第k小的元素并输出（分治算法）
2.解析
将S分为多个组q，每组5个元素，有剩余的话，则排序剩余元素。 将q个组单独排序，每组找出中项，中项组成集合M，以M中项n作为标准，将S划分为两个子数组S1和S2，把这个数组中比n小的都放入S1的数组中，数组S1的元素个数是|S1|个；把这个数组中比n大的都放入S2的数组中，数组S2的元素个数是|S2|个。
当要找的k<|S1|，就S1中找第k小的子问题。
当要找的k=|S1|+1， n=k。
当要找的k>|S1|+1，就在数组S2中找第k小的子问题。
3.设计
int Select(int *in,int L,int H, int s) {
int m = H+ 1 - L ;int n = m / 5;int * mo = (int*)malloc(sizeof(int) * n);if (m < max) {sort(in, L, H);// 进行排序return in[L + s];}for (int i = 0; i < n; i++) {sort(in, L + 5 * i, L + 5 * i + 4);mo[i] = in[L + 5 * i + 2];}int t1 = 0,t2 = 0,t3 = 0;int mid = Select(mo, 0, n, (n - 1) / 2), * a = (int*)malloc(sizeof(int) * m);int * b = (int*)malloc(sizeof(int) * m);int * c = (int*)malloc(sizeof(int) * m);for (int i = L; i <= H; i++) {if (in[i] = mid)b[t2++] = in[i];else if (in[i] > mid) c[t3++] = in[i];else a[t1++] = in[i];}if(t1 + t2 >= s)return mid;else if (t1 > s) return Select(a, 0, t1 - 1, s);else return Select(c, 0, t3 - 1, s - t1 - t2);
}
4.分析
最坏情况:
T(n)=O(n^2 )
一般情况：
T(n)=T(n/2)+n-1
T(n)=O(n)
5.源码
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 44
int sort( int *in,int L, int H);
int Select(int *in,int L,int H, int s);
int main() {
int n;
scanf("%d", &n);
int * in = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++) {scanf("%d", &in[i]);}int k ;scanf("%d",&k);printf("第k小素是：%d\n",Select(in, 0, n - 1, k-1));return 0;
}
int sort( int *in,int L, int H) {
for (int i = L; i <= H; i++) {
for (int j = L; j <= H - L - 1; j++) {
int temp;
if (in[j] >in[j + 1]) {
temp = in[j + 1];
in[j + 1]=in[j] ;
in[j]=temp;
}
}}
}
int Select(int *in,int L,int H, int s) {
int m = H+ 1 - L ;int n = m / 5;int * mo = (int*)malloc(sizeof(int) * n);if (m < max) {sort(in, L, H);return in[L + s];}for (int i = 0; i < n; i++) {sort(in, L + 5 * i, L + 5 * i + 4);mo[i] = in[L + 5 * i + 2];}int t1 = 0,t2 = 0,t3 = 0;int mid = Select(mo, 0, n, (n - 1) / 2), * a = (int*)malloc(sizeof(int) * m);int * b = (int*)malloc(sizeof(int) * m);int * c = (int*)malloc(sizeof(int) * m);for (int i = L; i <= H; i++) {if (in[i] = mid)b[t2++] = in[i];else if (in[i] > mid) c[t3++] = in[i];else a[t1++] = in[i];}if(t1 + t2 >= s)return mid;else if (t1 > s) return Select(a, 0, t1 - 1, s);else return Select(c, 0, t3 - 1, s - t1 - t2);
}
