数据结构之树和图算法.ppt
《数据结构之树和图算法.ppt》由会员分享,可在线阅读,更多相关《数据结构之树和图算法.ppt(70页珍藏版)》请在三一文库上搜索。
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)。,快速排序是一种不稳定的排序方法。,思想: 每一趟都选出一个最大或最小的元素,并放
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法
链接地址:https://www.31doc.com/p-2157146.html