共计 1455 个字符,预计需要花费 4 分钟才能阅读完成。
#include <iostream>
#define swap(a,b) (a)^=(b);(b)^=(a);(a)^=(b);
using namespace std;
void output(int * input, int p, int size){for(int i = p ; i < size; i++){cout<<" "<<input[i];
}
cout<<endl;
}
int sort(int* A, int p, int r) {
int j = p;
//output(A, 10);
for(int i = p+1; i < r; i++) {int insert = A[i];
int k = j;
for(; k >= p; k--) {if(A[k] > insert) {A[k+1] = A[k];
} else {break;}
}
A[k+1] = insert;
j++;
}
output(A, p, r);
int mid = (r-1-p)/2;
return A[p+mid];
}
int partition(int* A, int p, int r, int kv) {
int main = r-1;
for(int i = p; i < r; i++) {if(A[i]==kv) {main = i;}
}
cout << "main:"<<main<<endl;
swap(A[main], A[r-1]);
output(A, p, r);
int i = p-1, j = p;
while(j < r-1) {if(A[j] < A[r-1]) {
i++;
if(i!=j) {swap(A[i], A[j]);
}
}
j++;
}
swap(A[i+1], A[r-1]);
output(A, 0, r);
return i+1;
}
int kselect(int* A, int p, int r, int k) {if(r - p < 5) {sort(A, p, r);
return A[p+k-1];
}
int groups = (r-p)/5, i = 0;
int mid[groups+1] = {0}, midValue[groups+1] = {0};
for(; i < groups; i++) {
//cout<<p+i*5<<" "<< p+i*5+5<<endl;
midValue[i] = sort(A, p+i*5, p+i*5+5); // 各 group 中位数
}
if((r-p)%5 > 0) { // 解决余数局部
midValue[i] = sort(A, p+i*5, r);
}
output(A, p, r);
output(midValue, 0, groups+1);
int middestValue = sort(midValue, 0, sizeof(midValue)/sizeof(int));
cout << "middestValue:" << middestValue<< endl;
int q = partition(A, p, r, middestValue);
int num = q - p + 1;
cout<<"q:"<<q<<"num:"<<num <<"k:"<<k<<endl;
if(num == k) {return A[q];
} else if(num > k) {return kselect(A, p, q-1, k);
} else {return kselect(A, q+1, r, k-num);
}
return 0;
}
int main()
{
cout << "Hello World"<< endl;
int input[] = {1,3,2,10,5,11, 12, 8 ,6, 7};
//sort(input, 0, 10);
int mid = kselect(input, 0, sizeof(input)/sizeof(int), 8);
cout <<"ret:"<< mid;
return 0;
}
正文完