算法导论练习题7-6

算法导论习题7-6

题目：

考虑这样一种排序问题,即无法准确的知道等排序的各个数字到底是多大.对于其中的每个数字,我们只知道它落在实轴上的某个区间内.亦即,给定的 n 个形如[ai, bi ]的闭区间,其中ai,≤bi .算法的目标是对这些区间进行模糊排序(fuzzy-sort),亦即,产生各区间的一个排序<i1, i2, i3, i4,…in >,使得存在一个 cj ∈[ai, bi ],满足c1≤c2≤…≤cn .a)为n个区间的模糊排序设计一个算法,你的算法应该具有算法的一般结构,它可以快速排序左部端点(即各ai),也要能充分利用重叠区间来改善运行时间.(随着各区间重叠得越来越多,对各区间的排序的问题会变得越来越容易,你的算法应该能充分利用这种重叠.)b)证明: 在一般情况下,你的算法的区望运行时间为 O(n*lgn),但当所有的区间都重叠时,期望的运行时间为O(n) (亦即,当存在一个值 x, 使得对所有的i, 都有x∈[ai, bi ] ).你的算法不应显式的检查这种情况,而是应当随着重叠量的增加,性能自然地有所改善.

思考：

借用快排的划分思路，以某个元素为主元，把区域划分成三段，第一段都小于主元，第二段都等于主元

重点是划分，区间如果重叠的部分，就把它们看做是相等的，并提取公共部分继续划分

a.nodeb < b.nodea ==> a < b

a.nodea > b.nodeb ==> a > b

其它情况 ==> a = b

为了避免类似于(2,2) (7,7) (1,8)这样的情况，相等时要提取公因子，并更新主元（主元不一等是某个元素）

本代码采用面向对象思路对Node的操作进行了封装，Node.h对Node的操作进行了封装：

 

#include<iostream>using namespace std;#define Max 100class Node{private:int nodea;int nodeb;public://无参构造函数Node(){nodea=-1;nodeb=-1;}//带参构造函数Node(int a,int b):nodea(a),nodeb(b){}//判断区间根主元区间的大小bool operator <(const Node Na)const{if(nodeb<Na.nodea)return 1;return 0;}bool operator >(const Node Na)const{if(nodea>Na.nodeb)return 1;return 0;}bool operator ==(const Node Na)const{if((nodea<=Na.nodeb&&nodeb>=Na.nodea)){return 1;}return 0;}void Init(Node Na){if(Na.nodea>Na.nodeb){cout<<"wrong num!"<<endl;return;}nodea=Na.nodea;nodeb=Na.nodeb;}int Getnodea(){return nodea;}int Getnodeb(){return nodeb;}void Swap(Node *Na){Node temp;temp.nodea=Na->nodea;Na->nodea=nodea;nodea=temp.nodea;temp.nodeb=Na->nodeb;Na->nodeb=nodeb;nodeb=temp.nodeb;}void Setnodea(int a){nodea=a;}void Setnodeb(int b){nodeb=b;}void Swapnode(){int temp;temp=nodea;nodea=nodeb;nodeb=temp;}};

ReginSort.h实现了对数组区间进行模糊排序的功能，排序的依据是在排好序的数组的每一个区间中可以找到一个数字，这些数字为有序排列：

#include"Node.h"#include<iostream>using namespace std;//将区间分三段打印//打印分段为[0,na],[na+1,nb-1],[nb,lengtha-1]void Print(Node*a,Node b,int lengtha){int i,na,nb;na=b.Getnodea();nb=b.Getnodeb();//如果存在第一段则打印，即打印小于主元的区间if(na>=0){for(i=0;i<=na;i++){cout<<"["<<a[i].Getnodea()<<","<<a[i].Getnodeb()<<"] ";}cout<<endl;}//如果存在第二段则打印，即打印等于主元的区间if(nb>=0){for(i=na+1;i<nb;i++){cout<<"["<<a[i].Getnodea()<<","<<a[i].Getnodeb()<<"] ";}cout<<endl;}//打印大于主元的区间if(nb>=0&&nb<lengtha){for(i=nb;i<lengtha;i++){cout<<"["<<a[i].Getnodea()<<","<<a[i].Getnodeb()<<"] ";}cout<<endl;}cout<<endl;}//对区域的划分，算法的关键部分，按照选定的主元进行划分//返回划分的Node，nodea左边的为小于主元的，nodeb右边的为大于主元的，nodea和nodeb之间的为等于主元的Node DevideRegion(Node* a,int p,int r){Node devide,x;x=a[r];int i,j,k;i=p-1;j=r+1;k=p;while(k<=r&&k<j){//小于主元，该元素则放到相等区域的前面if(a[k]<x){i++;a[k].Swap(&a[i]);k++;}//在此判断语句中没有k++，因为a[j]与a[k]互换后，a[j]不一定比主元小//因此在下一次while循环中还要对刚刚换过来的a[j]进行比较else if(a[k]>x){j--;a[k].Swap(&a[j]);}//如果相等，则不交换，但可缩小主元区间，这样缩小的主元可以更加准确的划分数组else{x.Setnodea(max(a[k].Getnodea(),x.Getnodea()));x.Setnodeb(min(a[k].Getnodeb(),x.Getnodeb()));k++;}}//将划分后的区域界线赋给devideif(i>=0){devide.Setnodea(i);}if(j<=r){devide.Setnodeb(j);}Print(a,devide,r-p+1);return devide;}void RegionSort(Node* a,int p,int r){if(p<r){Node devide;devide=DevideRegion(a,p,r);int na=devide.Getnodea();int nb=devide.Getnodeb();//如果存在小于主元的区间则对该区间继续调用RegionSortif(na>=0){RegionSort(a,p,na);}//如果存在大于主元的区间则对该区间继续调用RegionSortif(nb>=0){RegionSort(a,nb,r);}}}

 

test.cpp对该算法进行了测试，所用的数组区间为随机产生，具有代表性

 

#include"RegionSrt.h"#include<iostream>using namespace std;int main(){Node A[10];int i,temp;//随机产生数组区间for(i = 0; i <10 ; i++) { A[i].Setnodea( rand() % 100); A[i].Setnodeb(rand() % 100); if(A[i].Getnodea() > A[i].Getnodeb()) {A[i].Swapnode();} } cout<<"the original region is :"<<endl;//输出原始数组for(i=0;i<10;i++){cout<<"["<<A[i].Getnodea()<<","<<A[i].Getnodeb()<<"] ";}cout<<endl<<endl;RegionSort(A,0,9);cout<<endl<<endl;//输出排序后数组for(i=0;i<10;i++){cout<<"["<<A[i].Getnodea()<<","<<A[i].Getnodeb()<<"] ";}cout<<endl;}

 

 

 

查看更多 下一篇