数据结构之树和图算法.ppt

1、设 n 个记录的序列为 R1 , R2 , R3 , . . . , Rn ,其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn ,此操作过程称为排序。,排序,假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；,若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的。,若在排序后的序列中 Rj 仍领先于 Ri ，则称排序方法是不稳定的。,例，序列 3 15 8 8 6 9,若排序后得 3 6 8 8 9 15,稳定的,若排序后得 3 6 8 8 9 15,不稳定的,稳定排序与不稳定排序,内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过

2、程。,外部排序: 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。,内部排序与外部排序,排序的时间复杂性,排序过程主要是对记录的排序码进行比较和记录的移动过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。,按照排序过程中所依据的原则的不同可以分类为:,插入排序,交换排序(快速排序),选择排序,归并排序,基数排序,二叉排序树排序,内

3、部排序,思想: 利用有序表的插入操作进行排序,有序表的插入: 将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。,例，序列 13 27 38 65 76 97,插入 49,13 27 38 49 65 76 97,插入排序直接插入排序,例，序列 49 38 65 97 76 13 27,初始，S = 49 ；, 38 49 ,初始，令第 1 个元素作为初始有序表；,依次插入第 2 , 3 , , k 个元素构造新的有序表；,直至最后一个元素；,直接插入排序算法主要应用比较和移动两种操作。,直接插入排序算法描述,void insertsort(ElemType R,int n) /待排

4、序元素用一个数组R表示，数组有n个元素 for ( int i=1; i=0) ,直接插入排序的效率分析,从空间来看，它只需要一个元素的辅助空间，用于元素的位置交换。 从时间分析，首先外层循环要进行n-1次插入，每次插入最少比较一次（正序），移动两次；最多比较i次，移动i2次（逆序）（i=1，2，n-1）。 Cmin=n-1 M min=2（n-1） Cmax=1+2+n-1=（n2-n）/2 M max=3+4+n+1=（n2+3n-4）/2 Cave=（n2+n-2）/4 M max=（n2+7n-8）/4 因此，直接插入排序的时间复杂度为O（n2）。 直接插入算法的元素移动是顺序的，该方

5、法是稳定的。,由于直接插入排序算法利用了有序表的插入操作，故顺序查找操作可以替换为折半查找操作。,例，序列 49 38 65 97 76 13 27,设已形成有序表 38 49 65 97 76 ,插入元素 13,折半插入排序,算法: void BinaryInsertSort(ElemType R,int n) for(int i=1; i=left;j-) Rj+1=Rj; /元素后移空出插入位 Rleft=temp; ,折半插入效率分析,二分插入算法与直接插入算法相比， 需要辅助空间与直接插入排序基本一致； 时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏， 两种方法的元素

6、的移动次数相同， 因此二分插入排序的时间复杂度仍为O(n2)。 二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。,分析直接插入排序,1. 若待排序记录序列按关键字基本有序，则排序效率可大大提高；,2. 待排序记录总数越少，排序效率越高；,希尔(shell)排序,思想:,先将待排序记录序列分割成为若干子序列分别进行直接插入排序；,待整个序列中的记录基本有序后，再全体进行一次直接插入排序。,例，序列 49 38 65 97 76 13 27 48 55 4 19,第一趟排序,13 19 49,27 38,48 65,55 97,4 76,第二趟排序,13 38 55 76,

7、4 27 49 65,19 48 97,第三趟排序,4 13 19 27 38 48 49 55 65 76 97,希尔排序的算法 template void ShellSort (T Vector, int arrSize ) T temp; int gap = arrSize / 2; /gap是子序列间隔 while ( gap != 0 ) /循环,直到gap为零 for ( int i = gap; i = gap; j -= gap ) if ( temp Vectorj-gap ) Vectorj = Vectorj-gap; else break; Vectorj = temp

8、; gap = ( int ) ( gap / 2 ); ,希尔排序效率分析,希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1.3）。,思想: 通过不断比较相邻元素大小，进行交换来实现排序。,首先将第一个元素与第二个元素比较大小，若为逆序，则交换；,然后比较第二个元素与第三个元素的大小，若为逆序，则交换；,. . .,直至比较第 n-1 个元素与第 n 个元素的大小，若为逆序，则交换；,第一趟排序:,结果:,关键字最大的记录被交换至最后一个元素位置上。,交换排序冒泡排序,例，序列 49 38 76 13 27,38 49 13 27,初始,第一趟排序后,最大值,次大值

9、,第二趟排序后,38 13 27,13 27,第三趟排序后,第四趟排序后,冒泡排序的算法实现。 void Bubblesort(ElemType R,int n) int flag=1; /当flag为0则停止排序 for (int i=1; i=i; j-) if (RjRj-1) /发生逆序 ElemType t=Rj; Rj=Rj-1; Rj-1=t;flag=1; /交换，并标记发生了交换 if(flag=0)return; ,冒泡排序的效率分析 从冒泡排序的算法可以看出，若待排序的元素为正序，则只需进行一趟排序，比较次数为（n-1）次，移动元素次数为0；若待排序的元素为逆序，则需进行

10、n-1趟排序，比较次数为(n2-n)/2，移动次数为3(n2-n )/2，因此冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。 因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。,冒泡排序的一种改进算法。,思想:,以首记录作为轴记录，从前、后双向扫描序列，通过交换，实现大值记录后移，小值记录前移，最终将轴记录安置在一个适当的位置。(小值记录在前、大值记录在后),轴记录将原序列分割成两部分，依次对前后两部分重新设定轴记录，继而分别再进行快速排序。,直至整个序列有序。,交换排序快速排序,快排序（Quick Sort),快速排序实例,快排序算

11、法思想,快排序（Quick Sort),快排序-分割过程 快排序是一个分治算法（也是第一个） 快排序的关键过程是每次递归的分割过程 分割问题描述：对一个序列，取它的一个元素作为轴，把所有小于轴的元素放在它的左边，大于它的元素放在它的右边 分割算法： 用临时变量对轴备份 取两个指针low和high，它们的初始值就是序列的两端下标，在整个过程中保证low不大于high 移动两个指针 首先从high所指的位置向左搜索，找到第一个小于轴的元素, 把这个元素放在low的位置 再从low开始向右，找到第一个大于轴的元素，把它放在high的位置,快排序（Quick Sort),快排序-分割过程 分割算法：

12、重复上述过程，直到low=high， 把轴放在low所指的位置 这样所有大于轴的元素被放在右边，所有小于轴的元素被放在左边,快排序（Quick Sort),快排序-分割过程,38 65 97 76 13 27 49,49,low,high,pivot = 49,0 1 2 3 4 5 6 7,high,38 65 97 76 13 49,27,low,27 38 97 76 13 49,65,high,27 38 97 76 65 49,13,low,27 38 13 76 65 49,97,high,49,快排序（Quick Sort),快排序-分割过程 int Partition(T Ar

13、ray, int low, int high) T pivot = Arraylow; / while(low = pivot) high -; Arraylow = Arrayhigh; while(low high ,快排序（Quick Sort),快排序-算法 快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为1,0 1 2 3 4 5 6 7,49 38 65 97 76 13 27 49,76 97 65 49,27 38 13,49,49,13,38,27,49 65,97,76,13 17 38 49 76 97,49 65,快排序（Quick Sort),

14、快排序-算法 void QuickSort(T Array, int low, int high) int PivotLocation; if(low high) PivotLocation = Partition(Array, low, high); QuickSort(Array, low, PivotLocation-1); QuickSort(Array, PivotLocation+1, high); ,3快速排序的效率分析,若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数n与二叉树深度h应满足log2nhlog2n+1 ，所以总的比较次数不会超过(n+1) log2

15、n。因此，快速排序的最好时间复杂度应为O（nlog2n）。而且在理论上已经证明，快速排序的平均时间复杂度也为O（nlog2n）。 若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有n-i个(i代表二叉树的层数（1in）元素，每层划分需要比较n-i+2次，所以总的比较次数为（n2+3n-4）/2。因此，快速排序的最坏时间复杂度为O(n2)。 快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。,快速排序是一种不稳定的排序方法。,思想: 每一趟都选出一个最大或最小的元素，并放

16、在合适当的位置。,简单选择排序,树形选择排序,堆排序,选择排序,思想:,第 1 趟选择:,从 1n 个记录中选择关键字最小的记录，并和第 1 个记录交换。,第 2 趟选择:,从 2n 个记录中选择关键字最小的记录，并和第 2 个记录交换。,第n-1趟选择:,从 n-1n 个记录中选择关键字最小的记录，并和第 n-1 个记录交换。,. . .,简单选择排序,例，序列 49 38 97 65 76,第 1 趟选择:,38 49 97 65 76,第 2 趟选择:,38 49 97 65 76,第 3 趟选择:,38 49 65 97 76,第 4 趟选择:,38 49 65 76 97,直接选择排

17、序的算法 template void SelectSort ( T Vector, int CurrentSize) for ( int i = 0; i CurrentSize-1; i+ ) int k = i; /选择具有最小排序码的对象 for ( int j = i+1; j CurrentSize; j+) if ( Vectorj Vectork ) k = j; /当前具最小排序码的对象 if ( k != i ) /对换到第 i 个位置 Swap ( Vectori, Vectork ); ,选择排序的主要操作是进行关键字间的比较。,在 n 个关键字中选出最小值，至少需要 n

18、-1 次比较。,在剩余的 n-1 个关键字中选出最小值，至少需要 n-2 次比较？,如果能利用前 n-1 次比较所得信息，可以减少后面选择的比较次数。,体育比赛中的锦标赛:,例，8 名运动员要决出 冠、亚、季军。,按简单选择排序需要比赛 7+6+5 = 18 场。,若能够利用以前的比赛结果，比赛场次实际可以减少为 11 场。,前提: 若 甲 胜 乙 ，乙 胜 丙 ，则 甲 必能胜 丙 。,冠军,如何求 亚军？,亚军,可以利用前面的比赛结果！,如何求 季军？,季军,同样可以利用前面的比赛结果！,又称锦标赛排序，是一种按照锦标赛的思想进行选择排序的方法。,例，序列 49 38 65 97 76 1

19、3 27 50,第一趟选择,最小值,树形选择排序,第二趟选择,次小值,第三趟选择,次次小值,缺点: 需要大量辅助存储空间,堆: 一棵完全二叉树，任一个非终端结点的值均小于等于(或大于等于)其左、右儿子结点的值。,例，,根结点为最小值,根结点为最大值,堆排序,2. 把这棵普通的完全二叉树改造成堆，便可获取最小值 ；,思想:,3. 输出最小值 ；,4. 删除根结点，继续改造剩余树成堆，便可获取次小值 ；,5. 输出次小值 ；,6. 重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序 。,1. 将序列构造成一棵完全二叉树 ；,例，序列 49 38 65 97 76 13 27 5

20、0,1. 按顺序依次构造成完全二叉树的结点；,2. 把完全二叉树改造成堆；,从下向上，父子交换；,3. 取得最小值 13,4. 删除 13 ，重新改造成新堆；,5. 取得次小值 27；,6. 删除 27 ，重新改造成新堆；,7. 取得次次小值 38；,归并排序（Merge Sort),归并-合并两个有序的序列 假设有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2) 方法很简单：把A，B两个序列的最小元素进行比较，把其中较小的元素作为C的第一个元素；在A，B剩余的元素中继续挑最小的元素进行比较，确定C的第二个元素，依次类推，就可以完成对A

21、和B的归并， 其复杂度为O(n),归并排序（Merge Sort),归并-合并两个有序的序列,A: 1 3 8 9 11,B: 2 5 7 10 13,C: 1 2 3 5 7 8 9 10 11 13,归并排序（Merge Sort),归并-合并两个有序的序列 void merge(T A, int Alen, T B, int Blen, T C) int i=0,j=0,k=0; while(i Alen ,归并排序（Merge Sort),归并-合并一个序列中的两个有序的数据段 void merge(T A, int l, int m, int h) int i=l,j=m+1,k=0

22、; T *C = new Th-l+1; while(i = m ,归并排序（Merge Sort),归并排序 归并排序是一个分治递归算法 递归基础：若序列只有一个元素，则它是有序的，不执行任何操作 递归步骤： 先把序列划分成长度基本相等的两个序列 对每个子序列递归排序 把排好序的子序列归并成最后的结果,归并排序（Merge Sort),归并排序,初始序列： 8，4，5，6，2，1，7，3,分解： 8 4 5 6 2 1 7 3,归并： 4，8 5，6 1，2 3，7,归并： 4，5，6， 8 1，2，3，7,归并： 1，2，3， 4，5，6，7，8,分解： 8，4，5，6 2，1，7，3,分

23、解： 8，4 5，6 2，1 7，3,归并排序（Merge Sort),归并排序 void MergeSort(int A, int l, int h) /将数组A中Al,(l+h)/2与A(l+h)/2+1,h两段数据归并 if(l = h) return; int m = (l+h)/2; MergeSort(A, l, m); MergeSort(A, m+1, h); Merge(A, l, m, h); ,归并排序（Merge Sort),算法分析 最坏情况：归并排序是一个递归算法，所以很容易得到算法计算量的递推公式 所以算法最坏情况的复杂度为 算法需要 的辅助空间,归并排序（Mer

24、ge Sort),其他策略 上面归并排序每次迭代时将原序列分割为两个基本等长的序列，称为二路归并排序 也可以分割成其他的分，如3，4等等 评论：尽管归并排序最坏情况的比较次数比快速排序少，但它需要更多的元素移动，因此，它在实用中不一定比快速排序快,归并排序（Merge Sort),以比较为基础的排序算法的下界 基于比较的算法总是在一系列比较下完成的 每次比较都可能出现两种情况(ab和ab), 如果以每次比较作为节点，则每个以比较为基础的排序算法都可以用一个二叉树来表示，其中一个中间节点表示一次比较，叶子节点表示排序的一种结果，这样的二叉树称为判定树或决策树 举例：比如有一个序列a, b, c(

25、a,b,c互不相等） ，下列算法： 先比较a和b, 再比较a和c，最后比较b和c 可以用下面的判定树表示,归并排序（Merge Sort),以比较为基础的排序算法的下界,ab?,yes,ac?,yes,bc?,yes,abc,acb,no,no,no,cab,ac?,yes,bac,no,bc?,yes,bca,cba,no,归并排序（Merge Sort),以比较为基础的排序算法的下界 假设输入为a,b,c, acb, 则算法执行经过的路线为(ab)(ac)(bc)，需要3次比较 假设输入为a,b,c, bac, 则算法执行经过的路线为(ab)(ac) 需要2次比较 任何以比较为基础的排序算

26、法都可以表示为一棵决策树 树的形状和大小表示的是排序算法的功能和需要排序的元素个数 树的高度表示了算法的运行时间 任何排序决策树都有n!个叶子,归并排序（Merge Sort),以比较为基础的排序算法的下界 根据数据结构中关于二叉树的性质，有： 最坏情况：任何排序算法至少要做 次比较 平均情况：任何排序算法的平均比较次数的下界是 结论：具有O(nlgn)复杂度的比较排序算法在渐进意义下是最优的算法,是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。,1. 多关键字排序,扑克牌问题 :,已知扑克牌中52张牌面的次序关系定义为:,例， 8 3,花色优先级更高，为主关键字，面值为次关键字,基

27、数排序,2. 52张牌排序方法 :,最高位优先法(MSDF) :,先按不同“花色”分成有次序的4堆，每一堆均具有相同的花色；,然后分别对每一堆按“面值”大小整理有序。,最低位优先法(LSDF) :,先按不同“面值”分成 13 堆 ；,然后将这 13 堆牌自小至大叠在一起( 2 , 3 , . . . , A ) ；,然后将这付牌整个颠倒过来再重新按不同的“花色”分成 4 堆 ；,最后将这 4 堆牌按自小至大的次序合在一起 。,收集,分配,3. 基数排序,基数排序就是借助于“分配”和“收集”两种操作实现对单逻辑关键字的排序。,首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。,其次，利用 LSDF 法实现对若干关键字的排序。,例，若关键字是数值，且值域为 0K999 ，,故可以将 K 看作是由 3 个关键字 K0 K1 K2 组成，,例，603是由 6 0 3 组成。,例，序列 278 109 063 930 589 184 505 269 008 083,第一趟分配,0 1 2 3 4 5 6 7 8 9,第一趟收集,930,063 083,184,505,278 008,109 589 269,第二趟分配,0 1 2 3 4 5 6 7 8 9,第