分治法求第k小元素
算法：http://www.cnblogs.com/chaofan/archive/2009/12/14/1623320.html
求一列数中的第k小元素，利用分治的策略进行递归求解。
首先随便指定一个数，这里我指定的是第一个数为第k小元素记为randK，将数组中其他的数与findK进行比较，比他小的放在左边，大的放在右边，如果randK左边的元素个数为k-1个，说明findK就是你所要找的元素，如果左边的元素个数>k-1，说明你要找的元素在左边的数中，继续使用相同的方法在左边的数中进行查找，如果左边的元素的个数<k-1,说明你要找的元素在右边的数中，则继续使用相同的办法在右边的数中进行查找。。。
代码：
#include <iostream>
using namespace std;
const int M = 999;
typedef struct Data
{
int data;
bool flag;
}Mit[M];
int findP(int a [], int oP, int R)
{
int randK = a[oP];
int iL = oP + 1;
int iR = R;
while (true)
{
while (a[iL] < randK)
{
iL++;
}
while (a[iR] >= randK)
{
iR--;
}
if (iL >= iR)
{
break;
}
swap(a[iL], a[iR]);
}
swap(a[oP], a[iR]);
return iR;
}
int findK(int a [], int oP, int n, int k)
{
int find_k;
int copy_k;
find_k = findP(a, oP, n);
copy_k = find_k - oP;
if (k == copy_k)
{
return a[find_k];
}
if (k > copy_k)
{
return findK(a, find_k + 1, n, k - copy_k - 1);
}
if (k > copy_k)
{
return findK(a, oP, find_k - 1, k);
}
else
{
return 0;
}
}
int main()
{
int n;
int k1, k2;
Mit d;
cout << "请输入无序列表的大小:" << endl;
cin >> n;
cout << "请输入无序列表中的所有元素" << endl;
//输入无序列表中的所有元素
for (int i = 0; i < n; i++)
{
d[i].flag = 1;
cin >> d[i].data;
}
cout << "请输入k1, k2:" << endl;
cin >> k1 >> k2;
if (k1 < k2)
{
int temp = k1;
k1 = k2;
k2 = temp;
}
for (int i = 0; i < n; i++)
{
if (d[i].flag)
{
cout << d[i].data << endl;
}
}
system("pause");
}/************************************************************************/
/* 分治法求第k小元素 */
/************************************************************************/
//在随机生成的数组中求第K小的元素，并求比较次数
#include<iostream>
#include<iomanip>
#include<ctime>
#define SIZE 100
#define swap(a,b) {int t=b;b=a;a=t;}
using namespace std;
static int cn = 2;//定义静态全局变量，统计比较次数
int partition(int a [], int l, int r)//返回中枢元素位置
{
int i = l - 1, j = r;
int v = a[r];//把中枢元素赋给V
while (1)
{
while (a[++i] < v)
cn++;
while (v < a[--j])
cn++;
if (i >= j)
break;
swap(a[i], a[j]);//交换元素
}
swap(a[i], a[r]);//交换中枢元素
return i;//返回排序后的中枢元素位置
}
int random_partition(int a [], int l, int r)//得到随机的中枢函数
{
srand(time(0));//初始化种子
int i = rand() % (r - l + 1) + l;//中枢元素随机划分
swap(a[i], a[r]);//把中枢元素放在开头位置
return partition(a, l, r);//返回中枢元素位置
}
int random_select(int a [], int l, int r, int k)
{
if (r <= l) return a[r];
int i = random_partition(a, l, r);//返回中枢元素位置
int j = i - l + 1;//求得元素个数
if (j == k)//判断是否为第K小，是则返回该元素
return a[i];
if (j > k)//小于第K小的元素个数多于K，则在左子集中寻找第K小的元素，否则在右子集中寻找
return random_select(a, l, i - 1, k);
else
return random_select(a, i + 1, r, k - j);
}
void disp(int a [], int n)//输出随机生成的数组元素
{
int k = -1;
for (int i = 0; i < n; i++){
k++;
if (k % 5 == 0)
cout << endl;
cout << setw(2) << i << ":" << setiosflags(ios::left) << setw(12) << a[i];
}
cout << endl;
}
int main()
{
int i, a[SIZE];//定义数组
srand((unsigned int) time(0));//初始化种子
for (i = 0; i <= 100; i++)
a[i++] = rand();//随机化数组
cout << "生成的随机数为:" << endl;
disp(a, SIZE);//输出生成的数组元素
int k;
cout << "------求第K小的数------" << endl;
cout << "请输入K:" << endl;
cin >> k;
cout << "第" << k << "小的数是:" << (random_select(a, 0, SIZE - 1, k)) << endl;
cout << "比较次数为:" << cn << endl;
return 0;
}#include<iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define Array_max 200
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void out(int a [], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
if (i%8 == 0 && i != 0)
{
cout << endl;
}
}
cout << endl;
}
int findP(int a [], int oP, int R)
{
int randK = a[oP];
int iL = oP + 1;
int iR = R;
while (true)
{
while (a[iL] < randK)
{
iL++;
}
while (a[iR] >= randK)
{
iR--;
}
if (iL >= iR)
{
break;
}
swap(a[iL], a[iR]);
}
swap(a[oP], a[iR]);
return iR;
}
int findK(int a [], int oP, int n, int k)
{
int find_k;
int copy_k;
find_k = findP(a, oP, n);
copy_k = find_k - oP;
if (k == copy_k)
{
return a[find_k];
}
if (k > copy_k)
{
return findK(a, find_k + 1, n, k - copy_k - 1);
}
if (k > copy_k)
{
return findK(a, oP, find_k - 1, k);
}
else
{
return 0;
}
}
void main()
{
int n;
int k;
Begin:
cout << "Please input the length of your Array:";
cin >> n;
cout << endl;
int *a = new int[n];
srand((unsigned) time(NULL));
for (int i = 0; i < n; i++)
{
a[i] = rand()%100;
}
cout << "The Random_Array_element is:" << endl;
out(a, n);
cout << "Please input the K:";
cin >> k;
if (k > n)
{
goto Begin;
}
else
{
cout << "The element you find now is:" << findK(a, 0, n - 1, k - 1) << endl;
}
system("pause");
}#include<iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
#define Array_max 200
void swap(int &a, int &b)
{
int temp;
temp = a;
a = b;
b = temp;
}
void out(int a [], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
if (i % 8 == 0 && i != 0)
{
cout << endl;
}
}
cout << endl;
}
int findP(int a [], int oP, int R)
{
int randK = a[oP];
int iL = oP + 1;
int iR = R;
while (true)
{
while (a[iL] < randK)
{
iL++;
}
while (a[iR] >= randK)
{
iR--;
}
if (iL >= iR)
{
break;
}
swap(a[iL], a[iR]);
}
swap(a[oP], a[iR]);
return iR;
}
int findK(int a[], int oP, int n, int k)
{
int find_k;
int copy_k;
find_k = findP(a, oP, n);
copy_k = find_k - oP;
if (k == copy_k)
{
return a[find_k];
}
if (k > copy_k)
{
return findK(a, find_k + 1, n, k - copy_k - 1);
}
if (k > copy_k)
{
return findK(a, oP, find_k - 1, k);
}
else
{
return 0;
}
}
void main()
{
int n;
int k1, k2;
Begin:
cout << "Please input the length of your Array:";
cin >> n;
cout << endl;
int *a = new int[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "The Random_Array_element is:" << endl;
out(a, n);
cout << "Please input the K1,k2(k1 < k2):";
cin >> k1>>k2;
if (k1 > n || k2 > n)
{
goto Begin;
}
else
{
int x = findK(a, 0, n - 1, k1);
int y = findK(a, 0, n - 1, k2);
int i;
/*cout << "The element you find now is:" << findK(a, 0, n - 1, k) << endl;*/
for (i = 0; i < n; i++)
{
if (a[i] != x ||a[i] != y)
{
a[i] = 0;
}
else
{
break;
}
}
for (i = n - 1; i > 0; i++)
{
if (a[i] != x || a[i] != y)
{
a[i] = 0;
}
else
{
break;
}
}
}
for (int i = 0; i < n;i++)
{
if (a[i] != 0)
cout << a[i] << " ";
}
system("pause");
}//在随机生成的数组中求第K小的元素，并求比较次数
#include<iostream>
#include<iomanip>
#include<ctime>
#define SIZE 100
#define swap(a,b) {int t=b;b=a;a=t;}
using namespace std;
static int cn=2;//定义静态全局变量，统计比较次数
int partition(int a[],int l,int r)//返回中枢元素位置
{
int i=l-1,j=r;
int v=a[r];//把中枢元素赋给V
while(1)
{
while(a[++i]<v) cn++;
while(v<a[--j]) cn++;
if(i>=j) break;
swap(a[i],a[j]);//交换元素
}
swap(a[i],a[r]);//交换中枢元素
return i;//返回排序后的中枢元素位置
}
int random_partition(int a[], int l, int r)//得到随机的中枢函数
{
srand(time(0));//初始化种子
int i=rand()%(r-l+1)+l;//中枢元素随机划分
swap(a[i],a[r]);//把中枢元素放在开头位置
return partition(a,l,r);//返回中枢元素位置
}
int random_select(int a[],int l,int r,int k)
{
if(r<=l) return a[r];
int i=random_partition(a,l,r);//返回中枢元素位置
int j=i-l+1;//求得元素个数
if(j==k)//判断是否为第K小，是则返回该元素
return a[i];
if(j>k)//小于第K小的元素个数多于K，则在左子集中寻找第K小的元素，否则在右子集中寻找
return random_select(a,l,i-1,k);
else
return random_select(a,i+1,r,k-j);
}
void disp(int a[],int n)//输出随机生成的数组元素
{
int k=-1;
for(int i=0;i<n;i++){
k++;
if(k%5==0)
cout<<endl;
cout<<setw(2)<<i<<":"<<setiosflags(ios::left)<<setw(12)<<a[i];}
cout<<endl;
}
int main()
{
int i,a[SIZE];//定义数组
srand((unsigned int)time(0));//初始化种子
for(i=0;i<=100;i++)
a[i++]=rand();//随机化数组
cout<<"生成的随机数为:"<<endl;
disp(a,SIZE);//输出生成的数组元素
int k;
cout<<"------求第K小的数------"<<endl;
cout<<"请输入K:"<<endl;
cin>>k;
cout<<"第"<<k<<"小的数是:"<<(random_select(a,0,SIZE-1,k))<<endl;
cout<<"比较次数为:"<<cn<<endl;
return 0;
} 相关推荐
koushr 2020-11-12
jimeshui 2020-11-13
faiculty 2020-08-20
数据与算法之美 2020-07-04
xhao 2020-06-29
wuxiaosi0 2020-06-28
路漫 2020-06-28
数据与算法之美 2020-06-28
田有朋 2020-06-28
xhao 2020-06-28
natloc 2020-06-27
leoaran 2020-06-22
算法改变人生 2020-06-09
nurvnurv 2020-06-07
shenwenjie 2020-06-04
Tips 2020-06-03
只能做防骑 2020-06-01
yuanran0 2020-05-13