k分为数

//选择算法有个线性算法，在此基础上改进，可以得到nlgk的分位点求法

//先求[k/2]那个分为点，然后在下面部分序列求前面的分为点，上边部分序列求后面的 //分为点，形如二叉树，可以达到lgk的高度，由于选择算法复杂度为n，所以整个 //复杂度为nlgk

#include #include

using namespace std;

int partition(int *A, int p, int r);

int Rondomized_Partition(int *A, int p, int r); int Rondomized_Select(int *A, int p, int r, int i); void Quantile(int *A, int p, int r, int k);

int main() { system(\"pause\"); return 0; }

int partition(int *A, int p, int r) { int x = A[r - 1]; int i = p - 1; for (int j = p; j <= r; j++) { if (A[j - 1] < x) { i++; int temp = A[j - 1]; A[j - 1] = A[i - 1]; A[i - 1] = temp; } } int temp = A[r - 1]; A[r - 1] = A[i];

A[i] = temp; return i + 1; }

int Rondomized_Partition(int *A, int p, int r) { int k = rand() % (r - p + 1) + p; int temp = A[r - 1]; A[r - 1] = A[k - 1]; A[k - 1] = temp; return partition(A, p, r); }

int Rondomized_Select(int *A, int p, int r, int i) { if (p == r) return A[p - 1]; int q = Rondomized_Partition(A, p, r); int k = q - p + 1; if (i == k) return A[q - 1]; else if (i < k) return Rondomized_Select(A, p, q - 1, i); else return Rondomized_Select(A, q + 1, r, i - k); }

void Quantile(int *A, int p, int r, int quantile) { if (0 == quantile) return ; int k = (r -p + 1) / quantile; B[k*quantile / 2 - 1] = Rondomized_Select(A, p, r, k*quantile / 2); Quantile(A, p, k*quantile / 2, quantile / 2); Quantile(A, k*quantile / 2, r, quantile / 2); }