• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-04-13)  算法/数据结构 |   抢沙发  22 
    文章评分 0 次,平均分 0.0

    a.简单排序算法

    简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写方便,适用于数据规模较小的情形。
    冒泡排序(Bubble Sort)的基本思路是:(以从小到大排序为例)从前到后逐个比较相邻两数,若前数大于后数,就将两数交换。不断重复这一过程,直至全部数字已按从小到大排好。
    考虑到实用性的问题,插入排序和选择排序这里不再介绍。
    对于NOIP提高组而言,这些算法时间复杂度过高,很难应付较大的数据规模。建议尽量不要采用简单排序算法,除非你十分确信数据规模在可承受范围之内。

    b.快速排序、堆排序

    快速排序和堆排序是比简单排序快的排序算法,在竞赛中常常被采用。这里,我们介绍快速排序算法。堆排序的实现不作介绍,若想了解,可咨询谷歌或百度。

    快速排序(Quick Sort)基于分治思想。它的基本思路是:(以从小到大排序为例)取一个数作为标记元素,将比它大的数放在它右侧,比它小的数放在它左侧,再通过递归的方法,将左侧的数用以上的方法排好,右侧的数也用以上的方法排好即可。
    在数据规模很大时,平均情况下快排比冒泡快很多。在处理NOIP提高组含排序的问题时,一般要选择快速排序或堆排序。

    下面将介绍快速排序的实现(以从小到大排序为例)。
    快排运用分治思想,因而要用函数的递归调用来实现:

    void QuickSort(int a[],int st,int stp) //这里也可以定义成void QuickSort(int *st,int len)。为了便于理解,我使用前一种写法。
    {
        int mid;
        mid=partition(a[],st,stp); //partition()用于确定标记元素的位置。
        if(l<mid-1)QuickSort(a[],st,mid-1);
        if(mid+1<r)QuickSort(a[],mid+1,stp);
    }

    现在的关键问题在于如何写partition()。

    写法一:对于数列                                                                                    5   6   7   5   3   8   1   6   2
    1.取首个元素做标记元素,取出它,令指针p指向最右边的数的右边——                                     _   6   7   5   3   8   1   6   2 p-
    2.将p向左移动到小于标记元素的数(或空缺处)为止。若指向空缺,则跳到5;否则将该数和p移到空缺处—— p-2   6   7   5   3   8   1   6   _
    3.将p向右移动到大于标记元素的数(或空缺处)为止。若指向空缺,则跳到5;否则将该数和p移到空缺处——   2   _   7   5   3   8   1   6 p-6
    4.重复2和3。                                                                                        2 p-1   7   5   3   8   _   6   6
                                                                                                        2   1   _   5   3   8 p-7   6   6
                                                                                                        2   1 p-3   5   _   8   7   6   6
    5.把标记元素放入空格处——                                                                          2   1   3   5 p-5   8   7   6   6

    写法二:写法二比写法一短一些,但理论上讲,写法二要慢一些(因为所作赋值运算多一些)。下面给出源代码与分析:

    void QuickSort(long a[],long st,long stp) //这里将partition()结合进QuickSort()中
    {
    	long t,n,l,r;
    
    	n=a[st];
    	l=st+1;
    	r=stp;
    
    	for(;;)
    	{
    		for(;a[l]<=n && l<=stp;l++); //从右找,找到一个小于标记元素的数
    		for(;a[r]>=n && r>st;r--); //从左找,找到一个大于标记元素的数
    
    		if(l>=r)break; //如果l在r右侧,则跳出
    		t=a[l];a[l]=a[r];a[r]=t; //交换,使小于标记元素的在左,大于标记元素的在右
    	}
    	a[st]=a[r]; //取出最右侧的小于标记元素的数写入空缺
    	a[r]=n; //空缺处放入标记元素
    
    	if(r-st>1)QuickSort(a,st,r-1);
    	if(stp>l)QuickSort(a,l,stp);
    }

    以上快排实现方法的最差情形是排列整齐的情况,这时它的运行效率会很低。为了解决排列整齐的情形,我们可以使用随机快速排序法,即随机选取一个数作为标记元素(实现时,将其与第一个数交换即可)。

    c.算法时空复杂度

    为了描述一个算法的优劣,我们引入算法时间复杂度和空间复杂度的概念。

    时间复杂度:一个算法主要运算的次数,用O()表示。
    通常表示时间复杂度时,我们只保留影响最大的项,并忽略该项的系数。
    例如主要运算为赋值的算法,赋值做了3n^3+n^2+8次,则认为它的复杂度为O(n^3);若主要运算为比较,比较做了4*2^n+2*n^4+700次,由于数据很大时,指数级增长的2^n影响最大,我们认为它的时间复杂度为O(2^n)。
    常见的时间复杂度有下列几个:
    O(n) ——贪心算法多数情况下为此时间复杂度
    O(nlbn) ——有时带有分治思想的算法的时间复杂度(注lbn表示以2为底的n的对数)
    O(n^2) ——有时动态规划的时间复杂度
    O(n^3) ——有时动态规划的时间复杂度
    O(2^n) ——有时搜索算法的时间复杂度
    O(n!) ——有时搜索算法的时间复杂度
    有时时间复杂度中含有两个或多个字母,比如遍历一个m*n的矩阵,时间复杂度为O(m*n)。
    要注意的是,时间复杂度相同的两个算法,它的实际执行时间可能会有数倍的差距,因而实现时要特别注意细节处的优化。

    NOIP提高组执行时限常常为1s。一般认为,将数据规模代入到时间复杂度,若所得值小于或接近于1000000,就是绝对安全的、不超时的。
    例如,O(n^2)的动态规划算法,可承受的数据规模是n≤1000;O(2^n)的搜索算法,可承受的数据规模是n≤20;O(n!)的搜索算法,可承受的数据规模是n≤9。
    实际上,以现在的CPU运行速度,5000000也应该不成问题。

    空间复杂度:一个算法消耗储存空间(内存)的大小,用O()表示。
    空间复杂度的表示规则与时间复杂度类似。
    在实际应用时,空间的占用是需要特别注意的问题。太大的数组经常是开不出来的,即使开出来了,遍历的时间消耗也是惊人的。

    下面我们简单地分析一下简单排序算法、快速排序、堆排序的时空复杂度。
    这三种算法都是基于比较的排序算法,以比较次数作为主要运算。
    简单排序算法最差时需做n^2次比较,平均情况下时间复杂度通常被认为是O(n^2)。
    快速排序最差时需做n^2次比较,可以证明平均情况下需做nlbn次比较,时间复杂度是O(nlbn)。
    堆排序时间复杂度是O(nlbn)。
    空间上,三者都不需要额外开辟暂存数组,快排递归调用时需要使用稍多一些的储存空间。
    综合来看,快速排序、堆排序优于简单排序算法。
    另外,可以证明基于比较的排序算法时间复杂度下界为O(nlbn)。

    d.时空的简单优化方法

    时间上的优化在于少做运算、做耗时短的运算等。
    有几个规律需要注意:
    整型运算耗时远低于实型运算耗时。
    +、- 运算非常快(减法是将减数取补码后与被减数相加,其中位运算更快一些,但是减法也比加法稍慢些。)
    * 运算比加法慢得多
    / 运算比乘法慢得多
    比较运算慢于四则运算
    赋值运算慢于比较运算(因为要写内存)
    这些规律我们可以从宏观上把握。事实上,究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编译器、系统决定。
    但是,少做运算(尤其在循环体、递归体中)一定能很大程度节省时间。

    下面来举一个例子:计算组合数C(m,n)——n件物品取出m件的组合数。
    C(m,n)可用公式直接计算。C(m,n)=n!/((n-m)!m!),C(m,n)=n(n-1)(n-2)…(n-m+1)/(n-m)!。显然,有时所作的乘法少很多,会快一些。
    可是这样算真的最快吗?
    另一条思路是C(m,n)=C(m,n-1)+C(m-1,n-1),递推下去,直到可利用C(1,k)=k=C(k-1,k)为止。我觉得这种只用加法的运算会快些,尽管加法多一些。(我没试验过,你可以去试一下。)

    空间上的优化主要在于减小数组大小、降低数组维数等。
    常用的节省内存的方法有:
    压缩储存——例:数组中每个数都只有0、1两种可能,则可以按位储存,空间压缩为原来的八分之一。
    覆盖旧数据——例:矩阵中每一行的值只与上一行有关,输出只和最末行有关,则可将奇数行储存在第一行,偶数行储存在第二行,降低空间复杂度。
    要注意的是,对空间的优化即使不改变复杂度、只是改变n的系数也是极有意义的。空间复杂度有时对时间也有影响,要想方设法进行优化。

    e.线性时间排序

    基于比较的排序算法时间复杂度下界为O(nlbn)。因而,若还要降低复杂度,要放弃基于比较的排序算法。
    有一类排序算法叫做线性时间排序,它们的时间复杂度为O(n)。下面介绍一种。
    计数排序思路:开辟暂存数组b[],b[k]表示欲排序数组a[]中k出现的次数(需要遍历a[]),最后遍历b[],可将a[]排好。
    这种想法非常简单,实现也很容易。事实证明,在a[]取值范围很小(如整型范围)时,它是很高效的排序算法,比快排快不少。可是a[]取值范围较大(如长整型范围)时,它的执行时间会变长,而且数组b[]有时开不出来。
    实际上计数排序时间复杂度为O(n+m),空间复杂度也为O(n+m),m表示a[]取值范围。若m很大,则也不能在时限内执行完。

    f.归并排序

    有一种排序时极为常见的情形:有一张成绩表,记录着许多学生的成绩,要将他们按成绩排序,但成绩相同者的相对顺序不能改变。
    换句话说,ABCDE五人,A、C、D成绩相同,显然排序完之后会排在一起,现在的要求是:他们排在一起的顺序也必须是ACD,不能是ADC、CAD…
    这样的实际问题涉及到排序的稳定性。
    排序的稳定性:一个排序算法,若可使排序前后关键字相同的项相对顺序不变,则称该排序算法是稳定的排序算法。

    下面我们来考察常见排序算法的稳定性。
    在编写合理的情况下,简单排序算法是稳定的;快速排序、堆排序是不稳定的(你可以好好想想这是为什么)。
    在NOIP中,往往排序是没有附带其他项目的,也就不要求排序稳定。快速排序、堆排序仍然是最佳选择。

    可是有没有时间复杂度为O(nlbn)的稳定的排序算法呢?有的。
    归并排序基于分治思想:把要排序的数组平分两半,对两部分分别排序(递归地)后再合并起来。合并时,将一个数组按顺序插入另一个数组中,需要开辟一个暂存数组。利用空间优化,可只用开辟一个与原数组等大的数组。
    归并排序的源代码会放在本章的附件中。请读者自己研究。
    归并排序的优缺点都很明显。无论情形如何,它的比较次数、赋值次数都稳定在nlbn,没有最差情况,运行时间与快速排序、堆排序相当。而且,它是稳定的排序算法。
    但是,它的内存占用回达到快速排序、堆排序的两倍,竞赛时使用容易造成内存超出限制。

    NOIP初赛曾考察过归并排序。问题大意是:找出一个算法,使五个数在n次比较(两两比较)后一定能排定次序,求n的最小值。
    在快速排序、堆排序的最差情况下,需要10次、9次比较。可是,使用归并排序只需要7次!记住:归并排序没有最差情况。

    g.合理选用排序算法

    下面是本章讲过的排序算法的优缺点比较:(这里只讲最主要的)

    排序算法 时间复杂度 优点 缺点
    简单排序 O(n^2) 编写方便 执行时间长
    快排 O(nlbn) 执行时间短 很差情况下执行时间长、占用内存多
    堆排序 O(nlbn) 执行时间短 编写有点麻烦,有较差的情况
    计数排序 O(n+m) 编写方便,取值范围小时很高效 取值范围大时效率低、易超内存限制
    归并排序 O(nlbn) 稳定的排序算法,无较差情况 占用内存很大

    竞赛中首选快速排序、堆排序。但有时也应比较各排序的优缺点,依实际合理选用。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/565.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享