数据结构第7章排序.ppt
《数据结构第7章排序.ppt》由会员分享,可在线阅读,更多相关《数据结构第7章排序.ppt(94页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数 据 结 构 第7章 排序概述概述什么是排序?排序是计算机内经常进行的一种操作,其目的是将一组“无序”的元素序列调整为“有序”的元素序列。假设含n个记录的序列为 R1,R2,,Rn,其相应的关键字序列为 K1,K2,,Kn。这些关键字相互之间可以进行比较,即在它们之间存在着这样一个关系:Kp1Kp2Kpn (或)按此关系将上面记录序列重新排列为:Rp1,Rp2,,Rpn 的操作操作称作排序排序。概述概述排序的分类按待排序元素关键字个数分单关键字排序多关键字排序按待排序元素的存储介质分内部排序:排序过程不需要访问外存便能完成外部排序:排序过程需要访问外存才能完成概述概述内部排序的类别插入类:直
2、接插入排序 折半插入排序 2-路插入排序 希尔排序分划类:冒泡排序 快速排序选择类:简单选择排序 堆排序归并类:2-路归并排序其他方法:基数排序概述概述排序的两个基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定性待排序列 a1,a2,an,其相应的关键字序列 k1,k2,kn,假设ki=kj(1i,jn且i j),且在排序前的序列中ai领先于 aj。若在排序后的序列中ai仍领先于 aj,则称排序结果是稳定的,反之,则称其是不稳定的。一种排序方法是稳定的,是指对任何序列的排序结果都是稳定的。一种排序方法是不稳定的,只要举出一个实例说明其排序结果是不稳定的即可。7.1 7.1 插入类
3、排序插入类排序插入类排序将待排序元素逐个插入到已排好序的有序表中,从而得到一个新的有序表。应用插入类排序思想的算法直接插入排序折半插入排序2-路插入排序希尔排序7.1.1 7.1.1 直接插入排序直接插入排序排序过程整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。第i趟直接插入排序的基本思想有序序列A0.i-1Ai无序序列 Ai.n-1有序序列A0.i无序序列 Ai+1.n-1直接插入排序例直接插入排序例7.1.1 7.1.1 直接插入排序直接插入排序直接插入排序算法/直接插入排序,数组data用于存放待排序元素,n
4、为待排序元素个数templatevoidInsertSort(ElemTypedata,intn)ElemTypetmp;inti,j;for(i=1;i=datai-1)continue;tmp=datai;/保存待插入的元素datai=datai-1;for(j=i-1;j0&dataj-1tmp;j-)dataj=dataj-1;/元素后移dataj=tmp;/插入到正确位置7.1.17.1.1直接插入排序直接插入排序算法评价时间复杂度最好情况(初始序列正序)元素比较次数:n-1元素移动次数:0最坏情况(初始序列逆序)元素比较次数:元素移动次数:平均情况O(n2)7.1.2 7.1.2
5、折半插入排序折半插入排序因为 A0.i-1 是一个按关键字有序的序列,则可以利用“折半查找”实现“在A0.i-1中查找Ai的插入位置”,如此实现的插入排序为折半插入排序。减少元素关键字间的比较次数,但元素移动次数不变。折半插入排序例折半插入排序例折半插入排序算法7.1.2 7.1.2 折半插入排序折半插入排序templatevoidBInsertSort(ElemTypedata,intn)ElemTypetmp;inti,j,mid,low,high;for(i=1;in;i+)tmp=datai,low=0,high=i-1;while(low=high)/在datalow.high中查找
6、插入的位置mid=(low+high)/2;/折半if(tmp=low;j-)dataj+1=dataj;/元素后移datalow=tmp;/插入到正确位置7.1.3 2-7.1.3 2-路插入排序路插入排序将插入区域分成大致等长的两段,选择性地插入到其中一段排序过程设置一个和原数组data 同类型,同规模的数组d,并将其视为循环数组(即位置n-1和0逻辑上相邻)d0=data0,将d0看作为排好序中处于中间位置的元素,从第二个元素data1开始做以下操作如果dataid0,将datai插入d0之后的有序序列,并保持插入后有序;反之,将其插入d0之前的有序序列,并保持插入后有序2-2-路插入排
7、序例路插入排序例7.1.4 7.1.4 希尔排序希尔排序希尔排序(又称缩小增量排序)将记录序列分成若干子序列,分别对每个子序列进行直接插入排序。例如:将 n 个记录分成 d 个子序列:R1,R1+d,R1+2d,R1+kd R2,R2+d,R2+2d,R2+kd Rd,R2d,R3d,Rkd,R(k+1)d 其中,d 称为增量,它的值在排序过程中从大到小逐渐缩小,直至最后一趟排序减为 1。希尔排序例希尔排序例 34288179 22165524996446设增量d=516282479 22345581996446设增量d=31622245528346446997981设增量d=11622242
8、8344655647981997.1.4 7.1.4 希尔排序希尔排序希尔排序算法templatevoidShellSort(ElemTypedata,intincrements,intn,intincrementsLength)inti,j,k;ElemTypetmp;for(k=0;kincrementsLength;k+)/进行以incrementsk为增量的排序for(i=incrementsk;i=incrementsk;j-=incrementsk)if(tmp=dataj-incrementsk)break;dataj=dataj-incrementsk;dataj=tmp;7.
9、1.4 7.1.4 希尔排序希尔排序特点子序列的构成不是简单的“逐段分割”,而是将相隔某个增量的元素组成一个子序列。希尔排序可提高排序速度,因为分组后n值减小,n更小,而T(n)=O(n),所以T(n)从总体上看是减小了。关键字较小的记录跳跃式前移,在进行最后一趟增量为1的插入排序时,序列已基本有序。7.1.4 7.1.4 希尔排序希尔排序算法评价算法效率依赖于增量序列的选择时间复杂度在O(n3/2)到O(n7/6)之间增量序列的取法最后一个增量必须为1其他增量间保持“互质”7.2 7.2 分划类排序分划类排序分划类排序通过一趟划分确定一个元素在序列中的位置,保证在它之前的一组元素不比它大,之
10、后的不比它小,接着对两组元素继续分划,直至待排序列有序。应用分划类排序思想的算法冒泡排序快速排序7.2.1 7.2.1 冒泡排序冒泡排序排序过程将第一个和第二个元素的关键字进行比较,若为逆序,则将两个元素互换;接着比较第二个和第三个元素的关键字,依次类推,直至最后两个元素的完成比较,这称为第一趟冒泡排序。第一趟排序分划出一组元素个数为n-1的待排序列和一个关键字最大的元素。第i趟对前n-i+1个的元素进行类似的排序操作,得到一组元素个数为n-i的待排序列和一个(在前n-i+1个元素中)关键字最大的元素。这样不断分划直至一趟分划时无元素互换为止。7.2.1 7.2.1 冒泡排序冒泡排序假设在排序
11、过程中,元素序列A0.n-1的状态为:无序序列A0.n-i有序序列An-i+1.n-1n-i无序序列A0.n-i-1有序序列An-i.n-1比较相邻记录,将关键字最大的记录交换到 n-i 的位置上第 i 趟冒泡排序冒泡排序例冒泡排序例7.2.1 7.2.1 冒泡排序冒泡排序冒泡排序算法templatevoidBubbleSort(ElemTypedata,intn)intlastSwapIndex=n-1;/用于记录最后一次交换的元素下标inti,j;for(i=lastSwapIndex;i0;i=lastSwapIndex)lastSwapIndex=0;for(j=0;jdataj+1)
12、Swap(dataj,dataj+1);lastSwapIndex=j;7.2.1 7.2.1 冒泡排序冒泡排序算法评价最好情况(正序)比较次数:n-1移动次数:0最坏情况(逆序)比较次数:n(n-1)/2移动次数:3n(n-1)/2平均 T(n)=O(n2)7.2.2 7.2.2 快速排序快速排序一趟快速排序选第一个待排序元素作为枢轴(或支点pivot),根据枢轴将待排序列划分为两个子序列。这两个子序列必须满足以下条件:一个子序列的元素关键字都不大于枢轴的关键字,另一个子序列的元素关键字都不小于枢轴的关键字。7.2.2 7.2.2 快速排序快速排序首先对无序的记录序列进行“一次划分”,之后分
13、别对分割所得两个子序列“递归”进行快速排序。无无 序序 的的 元元 素素 序序 列列无序子序列无序子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序7.2.2 7.2.2 快速排序快速排序排序过程对待排序列A进行快速排序的递归算法QuickSort(A)可以描述如下:如果A中元素的个数为0或1,则返回;否则,继续选取A中的一个元素p作为枢轴(pivot)将A中剩下的元素“划分”成两个不相交的集合:QuickSort(A1),QuickSort(A2)一趟快速排序例一趟快速排序例7.2.2 7.2.2 快速排序快速排序/对datalow.high进行分
14、划,确定枢轴的位置,并返回其所在位置/子序列中,在枢轴之前(后)的元素均不大(小)于它templateintPartition(ElemTypedata,intlow,inthigh)ElemTypepivot=datalow;/用子序列的头元素作为枢轴while(lowhigh)while(low=pivot)high-;datalow=datahigh;/比枢轴小的元素移到低端while(low=datalow)low+;datahigh=datalow;/比枢轴大的元素移到高端datalow=pivot;/确定枢轴的合适位置returnlow;/返回枢轴的位置一趟快速排序算法7.2.2
15、7.2.2 快速排序快速排序快速排序算法/对databegin.end进行快速排序templatevoidQuickSort(ElemTypedata,intbegin,intend)if(begin=end)/data长度小于等于1时返回return;intpivot=Partition(data,begin,end);/对databegin.end进行分划QuickSort(data,begin,pivot-1);/对低端子列进行递归排序QuickSort(data,pivot+1,end);/对高端子列进行递归排序/快速排序templatevoidQuickSort(ElemTypeda
16、ta,intn)if(n2)return;QuickSort(data,0,n-1);7.2.2 7.2.2 快速排序快速排序算法分析最好情况每次中间值作为枢轴T(n)=O(nlog2n)最坏情况每次总是最大或最小元素作为枢轴T(n)=O(n)平均情况T(n)=O(nlogn)三数中值分割法7.3 7.3 选择类排序选择类排序选择类排序逐趟扫描未排序的部分,从中选取一个元素移动到合适的位置。应用选择类排序思想的算法简单选择排序树形选择排序堆排序7.3.1 7.3.1 简单选择排序简单选择排序假设排序过程中,待排记录序列的状态为:有序序列有序序列A0.i-2无序序列无序序列 Ai-1.n-1第第
17、 i 趟简单选择排序趟简单选择排序从中选出关键字最小的从中选出关键字最小的元素元素有序序列有序序列A0.i-1无序序列无序序列 Ai.n-17.3.1 7.3.1 简单选择排序简单选择排序排序过程第一趟扫描所有待排序元素,找出关键字最小的元素并将它与第一个元素进行交换;第i趟,扫描待排序列中剩余n-i+1个元素,找出关键字最小的元素与序列中第i个元素交换;重复上述操作,直到所有的元素都放到正确的位置上为止。简单选择排序例简单选择排序例简单选择排序算法7.3.1 7.3.1 简单选择排序简单选择排序templatevoidSelectionSort(ElemTypedata,intn)inti,
18、j,min;for(i=0;in-1;i+)min=i;for(j=i+1;jn;j+)/选择datai+1.n-1中最小的元素if(datajdatamin)min=j;if(i!=min)Swap(datai,datamin);/将datai与第i小的元素交换7.3.1 7.3.1 简单选择排序简单选择排序算法分析最好情况比较次数:移动次数:0最坏情况比较次数:移动次数:3(n-1)平均 T(n)=O(n)7.3.2 7.3.2 树形选择排序树形选择排序简单选择排序中一趟排序中的比较操作可能在前一趟中已经做过,但前一趟中未保存这些比较结果,因此在后一趟的排序中又重复执行了这些操作。为了解决
19、这个问题,树形选择排序应运而生。树形选择排序(又称锦标赛排序)算法思想先将n个元素的关键字两两比较,然后将其中较小者两两比较,如此重复,不断的淘汰较大者,最终选出关键字最小的元素。树形选择排序例树形选择排序例例如:显然,比简单选择排序的比较次数少,但它需要增加辅助空间。7.3.3 7.3.3 堆排序堆排序堆的定义:堆是满足下列性质的数列a1,a2,,an:或(小顶/根堆)(大顶/根堆)12,36,27,65,40,34,98,81,73,55,49 小顶堆12,36,27,65,40,14,98,81,73,55,49 不是堆7.3.3 7.3.3 堆排序堆排序若将该数列视作完全二叉树,则 r
20、2i 是 ri 的左孩子;r2i+1 是 ri 的右孩子。aia2ia2i+11236276549817355403498不是堆不是堆14是小顶堆是小顶堆序列12,36,27,65,40,34,98,81,73,55,49147.3.3 7.3.3 堆排序堆排序堆排序即是利用堆的特性对记录序列进行排序的一种方法。建大顶堆98,53,55,18,4,22,2424,53,55,18,4,22,98交换 98 和 24重新调整为大顶堆55,53,24,18,4,22,98 22,18,53,98,4,24,55经过筛选7.3.3 7.3.3 堆排序堆排序排序过程将待排序列A0n-1建成大顶堆;将堆
21、顶元素A0(即关键字最大的元素)与堆尾元素(即堆中最后一个元素)交换,从堆中除去堆尾元素(即关键字最大的元素),同时调整堆中剩余元素,使它们恢复堆属性;反复进行步骤2,直至堆中元素个数为1。7.3.3 7.3.3 堆排序堆排序堆排序需解决的两个问题:如何将初始的待排序列建成一个堆?因堆顶元素与堆尾元素交换后,新的堆顶元素可能破坏了堆属性,如何再调整成为堆?第二个问题解决方法(大顶堆)输出堆顶元素之后,以堆中最后一个元素替代之;选左、右孩子中值大者(child)与根结点值比较,若child的值大于根的值,则进行交换;接着,以下调的结点为根,重复上述操作,直至根结点的值不小于孩子的值或根为叶子结点
22、,即得到新的堆。称这个调整过程为“筛选”。例例堆排序调整例堆排序调整例7.3.3 7.3.3 堆排序堆排序第一个问题解决方法从最后一个非叶子结点(即第 n/2个元素)开始依次往前,对所有非叶子结点做调整操作。建堆例建堆例 建堆是一个从下往上建堆是一个从下往上进行行“筛选”的的过程。程。40554973648136122798例如:排序之前的关键字序列为12368173499898494027 40,55,49,73,12,27,98,81,64,36 64817355361264调整堆算法7.3.37.3.3堆排序堆排序/将datai.n-1中的元素调整为大顶堆templatevoidHeap
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 排序
限制150内