// 利用随机化快速排序求带权中位数.cpp : Defines the entry point for the console application.
//
//中位数:n个元素集合中,第n/2小的元素,如果是偶数个,则选择中间二个的算术平均值。
//带权中位数:对于n个互不相同的元素集合x1、x2……xn,其权重依次为w1、w2……wn。按x值排好序后,
//从第一个元素的权值开始进行权值求和,第一个出现权值和大于等于所有元素的权值和的一半的元素
//先按利用随机化快速排序算法给关键字排序,然后从排序后元素0开始递推累加每个关键字的权,
//如果在某一个i时,累加的权大于等于总权的一半,那么这个i就是带权中位数的序号。
//随机化快速排序的平均时间为nlgn。
#include "stdafx.h"
#include "stdafx.h"
#include<iostream>
#include<ctime>
#define N 100
using namespace std;
struct Node
{
double value;
double weight;
};
Node nodes[N];
//产生一个随即下标,用其对应的数组元素作为比较标准(即一趟快速的主元)
int random(int m,int n)
{
srand((unsigned)time(NULL));
return m + (rand()%(n-m+1));
}
//一趟快速排序
int qartition(Node *nodes,int begin,int end)
{
int i = begin-1,j=begin;
double x = nodes[end].value;
while(j<end)
{
if(nodes[j].value<=x)
{
i++;
Node temp = nodes[i];
nodes[i]=nodes[j];
nodes[j]=temp;
}
j++;
}
Node temp = nodes[end];
nodes[end]=nodes[i+1];
nodes[i+1]=temp;
return i+1;
}
//一趟随机化快速排序
int random_qartition(Node *nodes,int begin,int end)
{
int q = random(begin,end);
Node temp = nodes[end];
nodes[end]=nodes[q];
nodes[q]=temp;
return qartition(nodes,begin,end);
}
//随机化快速排序
void random_fast_sort(Node *nodes,int begin,int end)
{
if(begin<end)
{
int p = random_qartition(nodes,begin,end);
random_fast_sort(nodes,begin,p-1);
random_fast_sort(nodes,p+1,end);
}
}
//得到带权的中位数
Node GetMidWeight(Node *nodes,int begin,int end,double SumWeight)
{
double midSum = 0.0;
int i;
for(i=begin;i<=end;i++)
{
midSum+=nodes[i].weight;
if(midSum>=SumWeight/2)
break;
}
return nodes[i];
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"请输入案例个数:"<<endl;
cin>>cases;
while(cases--)
{
cout<<"请输入数据个数:"<<endl;
int n;
cin>>n;
int i;
double sum = 0.0;
cout<<"请输入每一对值和其权值"<<endl;
for(i=0;i<n;i++)
{
cin>>nodes[i].value>>nodes[i].weight;
sum+=nodes[i].weight;
}
random_fast_sort(nodes,0,n-1);
cout<<"带权中位数为:"<<endl;
Node node = GetMidWeight(nodes,0,n-1,sum);
cout<<node.value<<endl;
cout<<"其权值为:"<<endl;
cout<<node.weight<<endl;
}
system("pause");
return 0;
}
分享到:
相关推荐
插入排序、冒泡排序、归并排序、快速排序四种排序方式的C++实现,各写成了一个函数,主函数中可以选择调用那一个。初始化数组时用的是随机种子srand((int)time(0))。在宏中定义数组大小。
在输入序列个数、排序情况不同的情况下对确定性快速排序与随机化快速排序的比较。比较他们的运行时间,验证是否与理论相符。
1)实现快速排序算法。 2)要求输入待排序元素个数,利用随机函数生成指定数目的元素,元素值的 取值范围为[10, 1000000]。 3)运行快速排序程序对所生成元素进行排序,要求将元素的初始输入序列和 排序后的结果序列...
单链表反序及求中位数的C++实现,初始化链表时用的是随机种子srand((int)time(0))。
最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...
(1)随机产生0到100之间的20个整数。 (2)输入序列,编写程序,用快速排序方法将序列从小到大排序并输出。 (3)纪录比较次数和移动次数。
快速排序的三种写法及随机主元快速排序时间复杂度是nlgn,
快速排序算法的C++实现,采用随机数作为基准
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
c++迭代实现快速排序。随机产生一定范围内的随机数,进行快速排序。
可以用递归快速实现排序算法,简洁高效,算法复杂度比较合理
三种排序算法(直接插入、冒泡、快速)的C++实现。有讲解
快速排序算法的基本思想是:随机选取数组中的一个值,将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直到...
能够将用户给定的值生成一个随机数组然后进行排序,递归实现
随机生成10000数字,进行快速排序,并输出排序后的数组,及耗时
严奶奶《数据结构》书上快速排序的C++算法实现,随机生成10个100以内的数,然后快速排序,并输出比较次数
随机森林的C++实现,附实现PPT和实验报告声明
可实现两个计算机间通信 并实现快速排序算法 2分钟内可排1000万个数 数是随机产生的
参照Sartaj Sahni所著的,Algorithms, and Applications in c++>>提供的代码,完成一个在VC++ 2010环境下调试通过的快速排序源程序。 代码非常简洁,十几行, 注释丰富,一看就懂,同时提供随机生成1000个整数为样例...
快速排序 C语言实现 快速排序 C语言实现 快速排序 C语言实现