经典ACM算法合集经典ACM算法合集(2)

经典ACM算法合集经典ACM算法合集

，先对这n个数排序，再用后面的数减去前面的数，即可求出相邻两数的差值，找出差值中最大的即为最大差值。

3、算法设计：
a. 用快速排序算法对这n个数排序，快速排序算法是基于分治策略的一个排序算
法。其基本思想是，对于输入的子数组a[p:r]，按以下三个步骤进行排序：
①分解：以a[p]为基准元素将a[p:r]划分为3段a[p:q-1]，a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[p]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。
②递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。
③合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和
a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。
b. 用函数maxtap()求出最大差值。

4、源程序：

#include<iostream.h>
#include<stdio.h>
double a[1000000];

template<class Type>
void swap(Type &x,Type &y)
{
Type temp=x;
x=y;
y=temp;
}

template<class Type>
int Partition(Type *a,int low,int high)
{
Type pivotkey;
int mid=(low+high)/2;
if((a[low]<a[mid]&&a[mid]<a[high])||(a[low]>a[mid]&&a[mid]>a[high]))
swap(a[low],a[mid]);
if((a[low]<a[high]&&a[mid]>a[high])||(a[low]>a[high]&&a[mid]<a[high]))
swap(a[low],a[high]);
pivotkey=a[low];
int i=low;
int j=high+1;
while(true)
{
while(a[++i]<pivotkey);
while(a[--j]>pivotkey);
if(i>=j) break;
swap(a[i],a[j]);
}
a[low]=a[j];
a[j]=pivotkey;
return j;
}

template<class Type>
void Quicksort(Type *a,int low,int high)
{
if(low<high)
{
int q=Partition(a,low,high);
Quicksort(a,low,q-1);
Quicksort(a,q+1,high);
}
}

template<class Type>
Type maxtap(Type *a,int n)
{
Type maxtap=0;
for(int i=0;i<n-1;i++)
maxtap=(a[i+1]-a[i])>maxtap?(a[i+1]-a[i]):maxtap;
return maxtap;
}

main()
{
int i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%lf",&a[i]);
Quicksort(a,0,n-1);
printf("%lf",maxtap(a,n));
return 0;


5、算法分析：
快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含n-1个元素和1个元素的时候。由于函数Partition的计算时间为O（n），所以如果算法Partition的每一步都出现这种不对称划分，则其计算时间复杂性T（ｎ）满足:

解此递归方程可得。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(2)全文阅读和word下载服务。