设为首页收藏本站
机战Z2破界篇 星组汉化 下载

星组游戏论坛

 找回密码
 注册(QQ注册+邀请注册)

QQ登录

只需一步,快速开始

查看: 1844|回复: 4

[心得] 排序算法的稳定性和时间、空间复杂度 [复制链接]

Rank: 11Rank: 11Rank: 11Rank: 11

UID
95322
星币
42
积分
27
阅读权限
90
注册时间
2012-12-13
最后登录
2013-5-9
发表于 2013-4-1 16:34:01 |显示全部楼层
本帖最后由 liu_jw 于 2013-4-1 16:34 编辑
" @- a6 m: M. O/ F) u6 |- R9 W1 [2 t3 A4 J7 t! A0 K/ k6 j$ e
     对于算法,大家在使用过后总会去考虑性能的问题。当然常说的是稳定性和时间、空间复杂度,刚开始还不知道是肿么回事,于是默默的问了问度娘,作以下总结:# J- A, K* z% x. a& ]  f- y
   1. 算法的稳定性:通俗点讲就是排序前两个相等的数在排序后在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。
) p( U. O' ?6 y0 Q# P      稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。8 F- {1 e5 y4 J$ Z; `
    2.时间复杂度:它主要是分析关键字的比较次数和记录的移动次数。: N* s1 [; h$ Q$ J" j# {- k. Q' a
             2.1 时间频度
; e# N. P+ Z$ n* O' H; X! ~                一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
4 ~1 k5 j( p, d! x             2.2 时间复杂度! j: H3 T5 c6 m+ h& e
         一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。$ Y1 s# K* K8 |, ?- E6 O
        在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如 T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
. i0 \" u4 i# |; \; |& b7 L; E" m' f         按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。  |  s$ \+ p1 e% J) A: S3 C  l
         随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
% ]7 l, r4 Y. Y4 h& H   3、空间复杂度) i# p! `# j: @4 x; N# B% i. }
      一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。1 Z9 {5 W8 m+ V% d; \4 \
      一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变
6 |  |* P# k* J        一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小,它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小,它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1,这个1表不开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。9 U' X8 Q! |& H
      对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当=i自求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
/ \) f- X5 y! y  F0 h
7 g2 |1 i; P9 E4 T- s6 T$ E5 f好多理论,来点具体的:* w# N( m/ X: D" `3 I  Y. o
一、算法的稳定性# G3 I2 q) f5 f- Q: A
(1)冒泡排序
( @: t- O; N. d: X( }3 Z2 p0 |      冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是
; a* N  z) N4 {, D* m一种稳定排序算法。, B4 h5 X- a1 d9 W4 M
, y/ |9 d& Q, ?: [
(2)选择排序  f) y! a1 w6 o; n7 X

9 x+ v& f, i* @* U( s7 B1 s      选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。# N+ o% @  @! z1 [  f
! V" p# C. L8 t, r3 m1 L- Q6 j% n
(3)插入排序
3 e4 o  j# s  w2 E     插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。9 L; j# W+ I: {1 l4 z
! I. e8 ^6 g  G, `5 D# I0 }
(4)快速排序- a2 q2 P6 _6 [( p$ P
    快速排序有两个方向,左边的i下标一直往右走,当a <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a和a[j],重复上面的过程,直到i>j。交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 910 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。6 j" P: C8 {) V0 d2 H# [
; N* L0 V0 l9 p$ ~7 U$ P
(5)归并排序9 R$ J. z. ]8 `, q6 @. K& q! s
    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。( |* i- A' J5 e/ x4 @
* I7 O( I3 \" I
(6)基数排序$ y0 {2 I: L, L& z
   基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。
; H0 Z8 l# ^: @* I4 m5 |$ ?! w4 C* ]
5 n, k; e9 {! o" I
(7)希尔排序(shell)  y; u5 Q) R2 E  w3 ~* r
    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
# d1 [% o$ o0 C" ~8 P, V4 z. t  J
8 s# o, Z" F! J2 y! r- b7 g; ~(8)堆排序
- k% r! ]& e) ~, a, @  H   我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定就被破坏了。2 g0 E; T' K: ?8 k3 S
于是乎 # {; y8 o$ |( @, Z4 g- G/ A
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
/ B: g( {2 @, M9 B2 P   二、时间复杂度
3 d3 ~$ I4 R! |  
& `% J, e; s4 X+ e* o: m3 A

时间复杂度对照表

时间复杂度对照表
/ U+ X' _( S/ R9 S! o. D
  L+ |/ V% {2 y
2.1 冒泡排序是稳定的,算法时间复杂度是O(n ^2)。+ y4 B& E& \; D1 @5 v- I
2.2 选择排序(Selection Sort)   选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L交换位置。这样,经过i遍处理之后,前i个记录的位置已经是正确的了。   选择排序是不稳定的,算法复杂度是O(n ^2 )。   2.3 插入排序 (Insertion Sort)   插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置,使得L[1..i] 又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L和L[i-1],如果L[i-1]≤ L,则L[1..i]已排好序,第i遍处理就结束了;否则交换L与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程,共需要(a),(b),(c)三次插入。   直接插入排序是稳定的,算法时间复杂度是O(n ^2) 。  2.4 堆排序   堆排序是一种树形选择排序,在排序过程中,将A[n]看成是完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。   堆排序是不稳定的,算法时间复杂度O(nlog n)。   2.5 归并排序   设有两个有序(升序)序列存储在同一数组中相邻的位置上,不妨设为A[l..m],A[m+1..h],将它们归并为一个有序数列,并存储在A[l..h]。   其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。   2.6 快速排序   快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后,使得排序序列的长度能大幅度地减少。在冒泡排序中,一次扫描只能确保最大数值的数移到正确位置,而待排序序列的长度可能只减少1。快速排序通过一趟扫描,就能确保某个数(以它为基准点吧)的左边各数都比它小,右边各数都比它大。然后又用同样的方法处理它左右两边的数,直到基准点的左右只有一个元素为止。   快速排序是不稳定的,最理想情况算法时间复杂度O(nlog2n),最坏O(n ^2)。  2.7 希尔排序  在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为 增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。  希尔排序是不稳定的,其时间复杂度为O(n ^2)。

3 Q# }2 r# n3 r0 M) n           三、空间复杂度! n2 @: t0 A) c. r, n
           就现有的排序算法来看,排序大致可分为内部排序和外部排序。如果整个排序过程不需要借助外部存储器(如磁盘等),所有排序操作都是在内存中完成,这种排序就被称为内部排序。
9 i* u" c+ z0 }. g* {

如果参与排序的数据元素非常多,数据量非常大,计算无法把整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘),这种排序就被称为外部排序。

         外部排序最常用算法是多路归并排序,即将原文件分解称多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序,接下来再对多个有序的子文件进行归并排序。

就常用的内部排序算法来说,可以分为以下几类:
8 c$ z" u9 b( f: E选择排序(直接选择排序,堆排序) 交换排序(冒泡排序,快速排序) 插入排序(直接插入排序,折半插入排序,Shell排序) 归并排序 桶式排序


! a( v* w" j# H
已有 1 人评分星币 收起 理由
绝世爱笑 + 1 这样才算爱过~

总评分: 星币 + 1   查看全部评分

管理员

勇者

Rank: 24Rank: 24Rank: 24Rank: 24Rank: 24Rank: 24

UID
4
星币
347
积分
5129
阅读权限
255
注册时间
2007-6-30
最后登录
2018-10-22
发表于 2013-4-1 21:47:21 |显示全部楼层
不错~~ 辛苦了~
星组游戏开发组 急招游戏画师美工~~~详见链接点我进入招募贴

Rank: 11Rank: 11Rank: 11Rank: 11

UID
95861
星币
51
积分
27
阅读权限
90
注册时间
2013-1-5
最后登录
2013-4-19
发表于 2013-4-2 08:58:57 |显示全部楼层
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶

Rank: 11Rank: 11Rank: 11Rank: 11

UID
95061
星币
5191
积分
814
阅读权限
90
注册时间
2012-12-5
最后登录
2018-9-29
发表于 2013-4-2 09:26:22 |显示全部楼层
好长
Freely Tomorrow
头像被屏蔽

禁止发言

UID
109963
星币
27
积分
122
阅读权限
0
注册时间
2015-10-8
最后登录
2015-10-13
发表于 2015-10-12 06:11:36 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

Archiver|星组游戏论坛 ( 京公网安备110403080002 )  

GMT+8, 2018-10-23 15:33

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部