分治策略的有关问题

分治策略的问题
利用分治策略，在n个不同元素中找出第k个最小元素。
程序怎么编？

[解决办法]
所谓快速选择。。。
1、从n个元素中任意选择一个元素a
2、遍历n个元素，将它们分为大于k和小于k的2部分
3、如果小于a的元素数量为k-1个，则a就是解
4、如果小于a的元素数量大于等于k，则递归的对小于a的元素执行快速选择
5、如果小于a的元素数量小于k-1，设大于a的元素有nr个，则递归的对这nr个元素执行快速选择，但是修改求解的目标为k - (n - nr)

注:第1步选择元素a的算法一般为取n个元素的第一个，中间的和尾部的3元素中间的那个。
[解决办法]
YES.QuickSelection VS QuickSort
[解决办法]
[code=C/C++][/code]
/**/
#include <iostream>
using namespace std;


/*
 * 分治法==》选取第一个值为枢点.
 */
//辅助操作:swap
template<class T>
void exchange(T& m, T& n)...{
T tmp;
tmp = m;
m = n;
n = tmp;
}
//基本操作：partition.
template<class T>
int split(T array[], int low, int high )...{
int i = low;
for(int j=low+1; j<=high; ++j) //high-low 次比较
if(array[j] < array[low])...{
++i;
if(i != j)// 不急于交换两个元素的值直至在出现大于枢点值后再次出现小于枢点值的时候才执行交换.
exchange(array[i], array[j]);
}
exchange(array[low], array[i]); 
return i;
}
//划分步，治理步，组合步(融合在一起)
template<class T>
void quick_sort(T array[], int low, int high)...{
int k;
if(low < high)...{ //low == high时，只剩下一个单独的元素，无需划分。
k = split(array, low, high);
quick_sort(array, low, k-1);
quick_sort(array, k+1, high);
}
}
int main() {
 int test[] = ...{23, 234,12, 4, -12, 23,12, 43, -999};
 quick_sort<int>(test, 0, 8);
 cout << "从小到大输出数组的值：" << endl;
 for(int i=0; i<9; ++i)
cout << test[i] << " ";
 cout << endl;
 return 0;
}

[解决办法]

C/C++ code

#include <stdio.h>#include <stdlib.h>int FindMinK(int data[], int l, int r, int k){    int m = data[l+k-1], t = 0;    int i, j;    data[l+k-1] = data[r], data[r] = m;    for (i = l-1, j = l; j != r; ++j)        if (data[j]<m)            t=data[++i], data[i]=data[j], data[j]=t;    t=data[++i], data[i]=data[j], data[j]=t;    if (k==i-l+1) return m;    if (k>i-l+1) return FindMinK(data, i+1, r, k-i+l-1);    else    return FindMinK(data, l, i-1, k);}int main(){    int data[]={8,6,6,4,4,3,2,1};    for (int i = 1; i <= sizeof(data)/sizeof(data[0]); ++i)        printf("%d\n", FindMinK(data, 0, 7, i));    return 0;}