以下是通过将数组划分为5组来实现中值的伪代码
select(int A[],int first, int last, int i) {
n = last - first + 1; /* n is the number elements to select from */
if (i > n) {return ERROR;} /* there is no ith smallest element */
if( n < = 100 ) {
/********************* For Small n *********************/
Run selection on A[first..last] taking at most n(n-1)/2 < 50n comparisons;
swap A[first+i-1] with A[first] /* put ith smallest in A[first] */
}
else /* n > 100 */ {
/********** main recursion *************************/
numGroups = n / 5; /* integer division, round down */
for group = 0 to numGroups-1 do {
shift = group*5;
/* A[first+shift] is the start of the group, A[first+shift+4] is end of group */
find median of A[first+shift .. first+shift+4] and swap it into A[first + group];
} /* for group */;
lastMedian = first+numGroups-1;
/* now the medians of the numGroups groups are all A[first .. lastMedian] */
/****** the first recursive call to find median of medians ******/
select(A, first, lastMedian, numGroups/2);
/* now median of medians is in slot A[first] */
/*********** partition array *********************/
k = partition(A,first, last); /* See partition on page 146 of text */
/* now k is the index where the median of median winds up, the smaller elements */
/* will be in A[first..k-1] and larger elements will be in A[k+1..last] */
/************ where is the ith smallest element? ********/
if (k == first + i -1) {
/* ith smallest is the median of medians in A[k] */
swap A[k] and A[first] and return
} else if (k > = first + i -1) {
/* second recursion to find ith smallest among the "small" keys in A[first..k-1] */
select(A, first, k-1, i);
} else /* k < first + i -1 */ {
/* second recursion to find the proper element among the "large" keys */
numSmaller = k-first+1; /* the number of "smaller" keys not recursed on */
newi = i - numSmaller;
/* the ith smallest of A[first..last] is the newi smallest of A[k+1..last] */
select(A, k+1, last, newi);
/* ith smallest now in A[k+1], put it in A[first] */
swap A[k+1] and A[first];
} /* if k - second else */
} /* if n - else part */
} /*select */
我有两个问题：
第一个与分区代码有关，这里只给出了数组及其边界，没有指示pivot元素，那么这个分区代码应该是什么样子呢？我们应该选择pivot索引和pivot元素作为：
int pivotindex=(end-begin)/2 int pivot values=a[pivotindex];还是应该是随机选择？
如何输出选定的中值？
一般来说，语言并不重要，但若能在C++中显示示例，那个就太好了。
可以在这里找到用于查找n中第k个最大整数的中值算法的解释：http://cs.indstate.edu/~spitla/presentation.pdf
c++中的实现如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMedian(vector<int> vec){
// Find median of a vector
int median;
size_t size = vec.size();
median = vec[(size/2)];
return median;
}
int findMedianOfMedians(vector<vector<int> > values){
vector<int> medians;
for (int i = 0; i < values.size(); i++) {
int m = findMedian(values[i]);
medians.push_back(m);
}
return findMedian(medians);
}
void selectionByMedianOfMedians(const vector<int> values, int k){
// Divide the list into n/5 lists of 5 elements each
vector<vector<int> > vec2D;
int count = 0;
while (count != values.size()) {
int countRow = 0;
vector<int> row;
while ((countRow < 5) && (count < values.size())) {
row.push_back(values[count]);
count++;
countRow++;
}
vec2D.push_back(row);
}
cout<<endl<<endl<<"Printing 2D vector : "<<endl;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
cout<<vec2D[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
// Calculating a new pivot for making splits
int m = findMedianOfMedians(vec2D);
cout<<"Median of medians is : "<<m<<endl;
// Partition the list into unique elements larger than 'm' (call this sublist L1) and
// those smaller them 'm' (call this sublist L2)
vector<int> L1, L2;
for (int i = 0; i < vec2D.size(); i++) {
for (int j = 0; j < vec2D[i].size(); j++) {
if (vec2D[i][j] > m) {
L1.push_back(vec2D[i][j]);
}else if (vec2D[i][j] < m){
L2.push_back(vec2D[i][j]);
}
}
}
// Checking the splits as per the new pivot 'm'
cout<<endl<<"Printing L1 : "<<endl;
for (int i = 0; i < L1.size(); i++) {
cout<<L1[i]<<" ";
}
cout<<endl<<endl<<"Printing L2 : "<<endl;
for (int i = 0; i < L2.size(); i++) {
cout<<L2[i]<<" ";
}
// Recursive calls
if ((k - 1) == L1.size()) {
cout<<endl<<endl<<"Answer :"<<m;
}else if (k <= L1.size()) {
return selectionByMedianOfMedians(L1, k);
}else if (k > (L1.size() + 1)){
return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
}
}
int main()
{
int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
vector<int> vec(values, values + 25);
cout<<"The given array is : "<<endl;
for (int i = 0; i < vec.size(); i++) {
cout<<vec[i]<<" ";
}
selectionByMedianOfMedians(vec, 8);
return 0;
}
select代码将中值分别放在。稍后，所需的i最小元素进入阵列的first插槽，因此分区的轴心，即中值，在A[first]中（在最末端，将是A[0]）。所以要输出，请读取此位置。
将伪代码转换为可编译代码非常简单，因为伪代码非常详细。唯一不明显的部分是n <= 100分支的代码、分区和中值5的查找。对于n <= 100分支，最简单的是使用与select相同的partition函数进行快速排序。要找到五个元素的中值，一个简单的排序算法是合适的，例如气泡排序、插入排序、香槟排序。
请自己尝试翻译，如果您有特殊困难，我们很乐意为您提供帮助。