【3】Chapter2程序性能2及数据结构基本概念.

1、2数据结构与算法授课教师：张剑波授课班级：114092-3班2010年秋李Chapter2程序性能C算比性能J2.1算法的重要特性及设计目标2.2程序（算法）性能的基本概念23程序（算法）时间复杂性分析2.4简单排序算法及效率分析2.5简单搜索（査找）算法及效率分析2.6程序（算法）空间复杂性分析2.4简单排序算法及效率分析【排序】将一组杂乱无章的数据按一定的规律顺次排列起来。重排训0,“1a|n-l使其形成递增（或者递滅） 次序.排序结束后，a0 = a|l| =a|n-l主要操作二比较移动常用排序算法计數擀序(Rank Sort)柚入4序(Insertion Sort)选择4序(Selec

2、tkm Sort)即池4序(Bubble Sort)箱排序( (Bin Sort)基数排序(Radix Sort )希尔排序(Shell Sort)堆排序( (Heap Sort )归并排序( (Merge Sort)快速排序(Quick Sort)6排序算法的分类内排序，指在排序期间数据对象全部存放在内存的 排序J外排序：指在排序期间全部对象个数太多，不能同 时存放在内存，必须根据排序过程的要求，不断在 内.外存之间移动的排序心内排序依不同原则分为：插入排序、交换排序、选 择排序、归并排序、基数排序等排序的性质排序的时间开销：是衡量算法好坏的最重要的标 志。排序的时间开销可用算法执行中的数据

3、比较 次数与数据移动次数来衡量排序方法的稳定性：如果在对象序列中有两个对 象ri和rj,它们的排序码ki = kj,且在排序之前，对象ri排在rj前面.如果在 排序之后，对象r订仍在对象r j的前面，则称 这个排序方法是稳定的，否则称这个排序方法是 不稳定的8内排序算法分类一：插入排序基本思想每步将一个待排序的对象，按其排序码 大小，插入到前面已经排好序的一组对象的适当位 置上，直到对象全部插入为止。常用算法：直接插入排序折半插入排序（二分法）希尔排序（缩小增量排序）:Shell内排序算法分类二：交换排序基本思想：是两两比较待排序对象的排序码，如发生逆序（即排列顺序与排序后的次序正好相反）,

4、则交换之，直到所有对象都排好序为止。常用算法:BubbleSort快速排序：Quicksort内排序算法分类三选择排序基本思想：每一趟(例如第i趟，i = 0,匚n 2)在后面个待排序记录中选出排序码最 小的记录，作为有序序列中的第i个记录。待到 第n 2趟作完，待排序记录只剩下1个，就不用再选了。常用算法：直接选择排序堆排序：HeapSort坦并：将两个或两个以上的有序表合并成一个新的有 序表。两路归并(2-way merging)：将原始序列中两个 有序襄initListJIinitListmn initListm +l . initListnj,它们可归并成一 个有序表。08 16 21

5、 25 25* 37 49 54 62 72 93内排initListmergeList本章用到的前序算法（1） -Max（程序1 31）templateint Max(T al，int n) / Locate the largest element in aO: pos = 0;for (int i = 1; i n; i+)if (apos ai)pos = i;return pos;寻找最大元素在数组中的位置11本章用到的前序算法（2） -Swap（程序1 11）templateinline void Swap(T&為T& b) / Swap a and b

6、.T temp = a;a = b;b = temp;交换两个值(1)计数排序算法uMi=ali;130112344393*71 |程序2-5:计算名次皿皿皿皿皿1 2413 1i 1程序2 6:按名次排序01231433*479待排序数组a老次数组F排序结 果数组U16按名次排序(程序2 6)关键操作：移动2n次使用附加数组u【小结】计数排序算法需要执行：(n-l)*n/2次比较操作 和2n次移动操作.是否可以不用附加数 组呢？-原地重排I按名次排序原地畫排数组元素012数组aL1 17i。名次01234数组rD a4while(r|i|!=i)int t=ri;Swap(ai?a(t);S

7、wap(ri,rt); tcmplatcvoid Rearrangc(T a9int njnt r)T匸newTfn+1;for(inti=0;in;i+)TTriJJ=anr#for(inti=O;in;i+)delete |u;18原地重排数组元素算法（程序2 11）templatevoid Rcarrangc(T aJnt ndnt r)for (int i=0;iii:i+)while(r|i!=i)关键操作int t=rfil; 原地重排数组：不使用附加 数组；最少交换次数：0（初始时 就已按序排列）；最大的交换次数：2（n-l）;毎次交换需要3次移动.17（2）直接选择排序【算法思

8、想】首 先找出最大的元素, 将其与afn-ll位置 交换；然后在余下的n 1个元素中寻找最 大的元素，将其与an-2|4i置交换，例. 如此进行下去直至n个元素排序完毕.初始元素序列:第一趟排序： 第二趟排序： 第三趟排序： 第四趟排序： 第五趟排序：第六趟排序：832 5 9 3* 6832 5 6 3* 913* 3256【89】3* 325【689】3* 32 1 5 6 8 9 12313* 5 68912 33*5 6 8 91920int pos = ft;_(int i = 1; i TT(a(pos ai) ),pos = i; dreturn pos;【缺点】：即使元素已 经

9、按序排列，程序仍然继 蛭运行.19及时终止的选择排序（程序2 12）templateclvoid SelcctionSortfT a9int n)/及时终止的选择排序bool sorted = false;for (int size = nTsortedX&(或恋 1 )；size)直接选择排序算法描述（程序2 7）template voidSelectionSort(T a?int n)sizc=n;sizc l;size-)关键操作: 比较次数=(n-l)+(n-2)+ +1=(n-l)*n/2移动次数：3（n-l）template intMax(T a9int n)int j=M

10、ax(a9size);Swap(aj,ssize-1 J); 思考：当数据元素为 已经排好序的情况下？比较21for (int i = 1; i 未痿序排列Swapialpos-, a|sizel J);22(3)冒泡排序趟数比较次数交换次数正序正序1n-1n-1112n-21In-i1n-111总计n-1(n-l)*n/21n-1(移动3(n-l)最坏情况下时间复杂性为：O(n2)最好情况下时间复杂性为：O(n)程序的渐进时间复杂性可由0(n)和0(以區示.及时终止的选择排序算法时间复杂性分析【算法思想】 采用“旨泡策略”把 最大元素移到右部初始元素序列：832593*6第一趟排序：325

11、83*69第二趟排序：235 3*61891第三趟排序：233* 5(689J第四趟排序：233*【5 6891第五趟排序：2313*5 689第六趟排序:2【33*5 6891*在冒泡过程中，对相邻元素进行比较， 如果左边的元素大于右:一趟冒泡结束 后，最大的元素被 排定.例冒泡排序算法描述（程序2 8, 2-9）一趟冒泡tcmplatebool Bubb!e(T a, int n)/空a0:n l中最吝匹素冒泡至右端swapped = fals巫力尚未发生交换fbr(int i = 0; i afi+l)上 wnp（3i|,合i 十丄）；泼生交换了teinplatevoid BubbleS

12、ort(T a9int n)/及时终止的冒泡排序for (int i = n; i 1 &BubhIe(a?i)i);胃泡排序templateai+l)Swap(ai, ai + 1);template/对數组aL0:n- 1J中的n个元素进行冒泡排序11及时终止的圖泡排序（程序2 13）relurn留泡排序 n个元素23 一趟圖例初始元素序列：832593*6第一趟排序：32583* 6 9第二趟排序：2353方6【89】第三趟排序：233* 5 6 89125冒泡排序算法：时间复杂性分析趟数比较次数交换次数正序正序1n-1n-10n-120n-20n-2I0n-i0n-in-101

13、01总计n-1(n-l)*n/20(n-l)+n/2,(移动次数：3(n-l)*n/2 )最坏情况下时间复杂性为：O(n2)最好情况下时间复杂性为：0(n)程序的渐进时间复杂性可由Q (n)和讥汩痢示.（4）插入排序【算法思想】每步将一个待排序元素，插入到前面已经排好 序的一组元素的适当位置上，直到全部元素插入为止.初始无素序列：18 32第一趟排序：【3 8】2第二趟排序：【2 38第三趟排序：【2 35第四趟排序：【2 3第五趟排序： 第六趟排序：3* 589【2 35 95 95 98 98 93*3*666663*3*6 2 3 3* 58 927正序和逆序情况下，数据元素的移动和比较

14、次数分别是多英？30插入排序算法时间复杂性分析趟数比较次数移动次数正序逆序正序逆序11122+121222+211122+iD-11n-122+(n-l)总计n-1(n-l)*n/22(n-l)(n-l)(4+n)/2最坏情况下时间复杂性为：0(1+2+.+n)=0(n2)最好情况下时间复杂性为：0(n)程序的渐进时间复杂性可由0 (n)和0($凄示.2.5简单捜索(查找)算法及效率分析【捜索】确定在数据元素的集合中是否存在一个数据等于给定码的过程。:常用32（1）廡序查找的 时间主要花在关键 码的比较上；（2）假设顺序表 中每个数据元素的 查找概率相同均为1/n;查找表中第i个数 据元素（i

15、=O,l,.n 1 ）所需进行的比 较次数为i+1,则（1）顺序捜索（查找） （程序2 1）x=24算法思想：从表的开始位置起，根据给定X的值， 逐个与表中各元素的值进行比较；若给定值与某个元素的值相等，则算 法报告查找成功，并返回该元素的位置；若查遍表中所有元素， 没有任何一个元 素的值和、相等，则算法扌艮告查找不成功并 返回1 31顺序tcmplateint SequentialSearch(T a9const T& xjnt n)成功查找return i; 34（2）有序顺序表的折半捜索又称为二分査找，是一种高效率的査找方法，但折半査找 有条件限制：（D衰必须用数组作存芒结构；（

16、2）表中元素必须按关键码有序（升序或降序均可）1、基本思想设有n个数据元素按其关键码从小到大的顺序存放在一个 顺序表中，先求出位于查找区间正中的数据元素的下标middle,用其关键码KEY与给定值的关键码v进行比较，比较 结果可能有三种：33KE=x查找成功;KEP.v,说明如采数据表中存在要找的数据元素，该数据 元素一定在mid的左锢，可把查找区间缩小到表的前半部分， 再继续进行折半查找；/CF.v,说明如果数据表中存在要找的数据元素，该数 据元素一定在mid的右侧，可把查找区间缩小到表的后半部 分，再继续进行折半查找；每比较一次，如果数据元素的关键码和给定值不相等，则 查找区间缩小一半，直

17、到查找区间已缩小到只有一个数据元 素，如果仍未找到想要的数据元素，則查找失败.例 设顺序表中有8个数据元素，它们的关键码依次为8, 14, 19,42, 48, 55, 72, 98,用折半捜索法在该表中搜索关键码为55和17的数据元素。A、给定值255的査找过程01234567814194248557298tt1low=0middle】=3high=701234567814194248557298low=4 middle2=5 high=735814194248557298low=0mid( (ile1=3high=7012345678141942485572981 I 1 low=0 mi

18、ddle2= 1 high=201234567814194248557298tttlow mid high通过三次比较，查找失败538templateint BinarySearch(T a9const T& x, int n) / Search a0| =a(ll=a(n-l| for x./ Return position if found; return -1 otherwise int left = 0; int right =n - 1;while (left amiddle) left = middle + 1;else right = middle 1; return -

19、1;x not found2.6程序(算法)空间复杂性分析算法的空间复杂性组成:指令空间(instruction space ):用来存储经过编译之后的 程序指令所需的空间.:数据空间(data space ):用来存储所有常量和所有变量值 所需的空间.:环境栈空间(environment stack space ):保存函数调用返 回时恢复运行所需要的信息。返回地址；函数被调用时所有局部变量的值以及传值形式参数的值；所有引用参数及常量引用参数的定义.有序表的折半捜索算法(程序2 30)最坏情况下总的时间 复杂度0(logn)40固定部分（C）:独立于实例的誉征飞冷指令空 间.简单变量及定长复

20、合变量.常量等等.可变部分（Sp）:般依赖于实例的持征。包含:复合变童所需空间（依赖于所解决的具体问題）;动态分配的空间（依赖于实例的特征）； 递归栈所需空间（依赖于实例特征）.任意程序P所需要的空间S（p）可以表示为:SWX+Sp（实例特征）点考虑Sp39空间复杂性举例1（程序2 1）teinplateint ScquentialSearcli(r?consT xnn)for(iOpn&ai!=x;i+); if(i=n) returreturn i;【顺序搜索算法】在未排序的数 组dO:n l中查找 与目等的元素.如果找到，则 返回与X相等的第 一个元素的位置；否則返回1 41设T为int, S(p)=4*6=24 BytesS櫃序搜素(n)=042空间复杂性举例2（程序1 7）int FactoriaKint n) 计算n!if(n=l) return 1;else return nFactioriaKn-l);*递归深度为max n-lwO:每次调用函数Factorial时，递归栈需要保留返回见址（4个字希）和n的社（4木字希）:SFaetortol（n） = 8*max n-lw041空间复杂性小结对非递归算法分析与实例特征有关的数据结构的大小复合变童对递归算法还要分析递归调用的深度和实例特征的关系环境栈地址参数变童