最大间隙问题

《最大间隙问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二最大间隙问题1、问题描述::大间隙问题:给定n个实数xl,x2，…，xn，求这n个数在实轴上相邻2个数之间的最大差值。假设对任何实数的下取整函数耗时0(1),设计解最大间隙问题的线性时间算法。对于给定的n个实数编程计算它们的最大间隙。2、题目分析:考虑到实数在实轴上按大小顺序排列，先对这n个数排序，再用后面的数减去前面的数，即可求出相邻两数的差值，找出差值中最大的即为最大差值。3、算法设计:a.用快速排序算法对这n个数排序，快速排序算法是基于分治策略的一个排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排

2、序：①分解：以a[p]为基准元素将a[p:r]划分为3段a[p:q-l],a[q]和a[q+l:r],使a[p:q-l]中任何一个元素小于等于a[p],而a[q+l:r]中任何一个元素大于等于a[q]o下标q在划分过程中确定。②递归求解：通过递归调用快速排序算法分别对a[p:q-l]和a[q+l:r]进行排序。③合并：由于对a[p:q-l]和a[q+l:r啲排序是就地进行的，所以在a[p:q-l]和a[q+l:r]都已排好的序后，不需要执行任何计算，a[p:r]Uc已排好用函数maxtapQ求出最大差值。4、源程序:#include<

3、iostream.h>#includedoublea[1000000];templatevoidswap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateintPartition(Type*a,intlow9inthigh)Typepivotkey;intmid=(low+high)/2;if((a[low]

4、

5、(a[low]>a[mid]&&a[midj>a[high]))swap

6、(a[low],a[mid]);if((a[low]a[high])

7、

8、(a[low]>a[high]&&a[mid]<班high]))swap(a[low],a[high]);pivotkey=a[low];inti=low;intj=high+l;while(true){while(a[++i]pivotkey);if(i>=j)break;swap(a[i],a[j]);}a[low]=a[j];a[j]=pivotkey;returnj;templ

9、atevoidQuicksort(Type*a,intlow,inthigh){if(lowTypemaxtap(Type*a，intn){Typemaxtap=0;for(inti=0;imaxtap?(a[i+l]-a[i]):maxtap;returnma

10、xtap;main()inti，n;scanf(H%dn,&n);for(i=0;i

11、每次划分所取得基准都恰好为中值，即每次划分都产生两个大小为n/2的区域，此时，Partition的计算时间T(n)满足：其解为。可以证明，快速排序算法在平均情况下的时间复杂性也是。