东南大学计算机学院方效林教学课件.ppt

《东南大学计算机学院方效林教学课件.ppt》由会员分享，可在线阅读，更多相关《东南大学计算机学院方效林教学课件.ppt（38页珍藏版）》请在三一办公上搜索。

1、东南大学计算机学院 方效林,本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件,第九章 排序,本章主要内容,排序的概念插入排序顺序插入排序折半插入排序希尔排序快速排序选择排序归并排序分配排序内部排序算法分析,2,排序的概念,定义将一组杂乱无章的数据按一定规律顺次排列数据表(dataList)待排序数据元素的有限集合排序码(key)通常数据元素有多个属性，作为排序依据的属性称为排序码学生成绩表，按学号小到大排序，按成绩高到低排序,3,排序的概念,排序的稳定性两数据元素排序码相同，排序前后两元素先后顺序若相同，则是稳定的若不同，则不稳定内排序和外排序内排序所有元素都在存在内存的排序外排序

2、数据太多，内存放不下，而存放在外部存储器，排序时需要经常在内、外存之间读写数据,4,初始,排序1,排序2,稳定的,不稳定,排序的概念,排序的时间开销内排序一般用数据比较次数和数据移动次数衡量外排序一般用外存的读写次数衡量(外存慢)排序的空间开销执行排序算法需要的存储空间,5,顺序插入排序,顺序插入排序算法将待排序元素，从后向前寻找适当的插入位置，直到所有元素都插入为止,6,插入25，25 21，无需移动,插入49，49 25，无需移动,插入25*，25*49，,插入16，16 49,25*,25,21，,插入08，08 49,25*,25,21,16，,49后移，25*填入,49,25*,25

3、,21后移，16填入,49,25*,25,21,16后移，08填入,顺序插入排序,算法分析最好情况(n个元素)原数据是按小到大顺序排好的每步只需与前一个数据比较一次，而不用移动数据总比较次数n-1，总移动次数0最坏情况(n个元素,i=0,1,n-1)原数据按大到小顺序排好的元素i需要比较i次，每比较1次移动1次，元素i移动2次总比较次数和总移动次数,temp=aia0=temp,比较和移动最坏最好平均值约为n2/4时间复杂度O(n2),顺序插入排序,算法分析是稳定的算法，key相同元素原来的顺序不会打乱需要额外一个存储空间,8,temp=aia0=temp,折半插入排序,折半插入排序算法将待排

4、序元素，按折半搜索法寻找适当的插入位置，直到所有元素都插入为止,9,lowhigh，49,25*,25后移，23填入,mid23,high=mid-1,mid=(low+high)/2,mid23,low=mid+1,mid=(low+high)/2,mid23,low=mid+1,mid=(low+high)/2,折半插入排序,算法分析平均情况下，折半搜索比顺序搜索快搜索元素i需比较log2i+1次总比较次数移动的时间复杂度O(n2)是稳定的排序算法，需额外一个存储空间,10,比较的时间复杂度O(n*log2n),希尔排序,基本思想设定不同gap值，距离gap的元素放一起插入排序,11,第1

5、步,gap=n/3+1=3,结果,gap=gap/3+1=2,结果,gap=gap/3+1=1,结果,第2步,第3步,最后1步是n个元素进行插入排序是不是很慢？,希尔排序,算法分析设定不同gap值，距离gap的元素放一起插入排序gap值越来越小，由于前面的排序过程，使得大多数数据已经基本有序，因此希尔排序速度仍然很快gap的取值方法有很多种gap=gap/3+1gap=gap/2希尔排序复杂度分析很困难，还没有完整的数学分析统计得出，平均比较和移动次数在n1.25,1.6n1.25内是不稳定的排序算法,12,快速排序,基本思想Partition：任取一元素x为基准(如选第1个)，小于x的元素放

6、在x左边，大于等于x的元素放在x右边对左、右部分递归执行上一步骤直至只有一个元素,13,初始,第1层,第2层,第3层,选21为基准,左部选08，右部选25*为基准,左部选16，右部选25为基准,第4层,右部选49为基准,快速排序,Partition(low,high)初始时基准坐标p=low,x=alow=21从i=low+1位置开始判断，比x小的元素与p下一个位置交换，p自加1循环直至i high，最后alow与ap交换,14,p,p,p,i,p,ihigh,停止,i,alow与ap交换,ai与ap+1交换,p+,ai与ap+1交换,p+,15,作业：对数据aN进行快速排序的程序qsort(

7、a,0,n-1),快速排序,性能分析快速排序是一个递归算法,16,递归树,快速排序,性能分析快速排序的趟数取决于递归树的深度若每次选取的基准可将序列划分成长度相近的左、右两部分，则下一层将对两个长度减半的序列排序设原序列有n个元素，选基准和划分所需时间为O(n)设整个快速排序所需时间为T(n)，则有：T(n)cn+2T(n/2)/c 是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(nlog2n),17,快速排序,性能分析快速排序平均计算时间为O(nlog2n)平均计算时间是所有内

8、部排序方法中最好的递归算法每层需保存递归调用的指针和参数平均情况下最大递归层数为log2(n+1)存储开销为O(log2n),18,快速排序,性能分析最坏情况单枝树，每次划分只得到比上一次少一个元素的序列比较次数递归树有n层，存储开销为O(n)快速排序是不稳定的算法,19,快速排序,改进算法快速排序对长度很小的序列排序并不比直接插入快长度取525时，直接插入法比快速排序法快10%改进方法1：在快速排序递归过程中，当序列长度小于一定值时，使用直接插入排序法改进方法2：在快速排序递归过程中，当序列长度小于一定值时，退出排序得到一个整体上几乎已经排好序的序列对这个几乎已经排好序的序列使用直接插入排序

9、法,20,快速排序,改进算法基准元素的选取对算法性能有很大影响改进方法1：可随机选择一个元素作为基准，避免最坏情况发生改进方法2：取左端点、右端点、中点(mid=(left+right)/2)这三个元素中的中间值作为基准,21,左端点,右端点,中点,取21，25*，08三个元素中的21为基准,选择排序,直接选择排序在待排序序列中选择最小的元素xx与第一个元素对换剔除x，对剩下元素执行以上步骤,22,初始,第1步,第2步,第3步,第4步,第5步,选择排序,直接选择排序算法分析设有n个元素，第i趟比较次数为n-i-1次总比较次数为移动次数最好情况为0最坏情况为3(n-1)直接选择排序是不稳定算法,

10、23,堆排序,算法思想建立最大堆循环执行以下步骤，直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆,i=2,最后一元素的父节点i=2开始调整,i=1,调整i=1,i=0,调整i=0,形成最大堆,堆排序,算法思想建立最大堆循环执行以下步骤，直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆,堆顶49与堆尾08交换,21,25,25*,16,49,08,21,49,25*,08,16,25,虚线内调整为最大堆,堆顶25与堆尾16交换,虚线内调整为最大堆,21,49,16,08,25,25*,堆顶25*与堆尾08交换,

11、虚线内调整为最大堆,堆排序,算法思想建立最大堆循环执行以下步骤，直至所有元素出堆每次堆顶元素(即最大元素)与堆中最后一个元素交换剔除最大元素后调整为最大堆,49,16,25*,25,21,堆顶21与堆尾08交换,虚线内调整为最大堆,08,49,25*,25,堆顶16与堆尾08交换,虚线内调整为最大堆,21,08,16,49,25*,25,虚线内调整为最大堆,21,16,08,堆排序,堆排序算法分析建立最大堆设堆中有n个元素,对应完全二叉树有k层(2k-1n2k)第i层向下调整移动距离最大为(k-i),第i层节点数为2i-1总移动次数循环弹出堆顶元素执行n-1次向下调整，每次调整距离log2(n

12、+1)总调整时间O(nlog2n),堆排序算法的计算时间复杂度为O(nlog2n)是不稳定排序,归并排序,算法思想将序列分成两个长度相等的子序列分别对两个子序列排序将排好序的两个子序列合并,28,21,25,49,25*,16,08,31,41,21,25,49,25*,16,08,31,41,归并排序,算法分析计算时间包括对两个子序列分别排序时间归并的时间T(n)=cn+2T(n/2)=O(nlog2n)最好、最坏、平均时间复杂度均为O(nlog2n)是稳定排序,29,桶式排序,基本思想输入：在0,1)区间内均匀分布的随机序列将区间0,1)划分成一系列桶(等长子区间)，如0,0.1),0.1

13、,0.2),0.9,1)对属于桶内的序列分别排序，按桶的编号依次输出,30,.72,.78,.12,.17,.21,.23,.26,.39,.68,.94,.78,.72,.17,.12,.26,.21,.23,.39,.68,.94,桶式排序,算法分析整个桶排序时间复杂度为将元素分配到各个桶中的时间复杂度为O(n)假设每个桶中序列使用直接插入排序，时间复杂度为O(ni2)极限情况下，每个桶放一个元素，桶排序最好效率为O(n),31,基数排序,多排序码排序花色：面值：2345678910JQKA排成以下序列就是多排序码排序2,A,2,A,2,A,2,A排序后的有序序列称为字典有序序列可先按花色

14、排序，再按字母排序也可先按字母排序，再按花色排序,32,基数排序,多排序码排序最高位优先(MSD,Most Significant Digit first)按第1排序码排序，会分成若干组递归对各组按第2,3,d排序码排序最后把所有子组元素依次连接起来形成有序序列最低位优先(LSD,Least Significant Digit first)按第d排序码(最低位)排序对上一排序结果按第d-1排序码(次低位)排序对上一排序结果按第d-2排序码排序，以此类推，直到按第1排序码完成排序，可得最终排序结果,33,基数排序,多排序码排序最高位优先(MSD,Most Significant Digit fi

15、rst)按第1排序码排序，会分成若干组递归对各组按第2,3,d排序码排序最后把所有子组元素依次连接起来形成有序序列,34,基数排序,最低位优先(LSD)按第d排序码(最低位)排序对上一排序结果按第d-1排序码(次低位)排序对上一排序结果按第d-2排序码排序，以此类推，直到按第1排序码完成排序，可得最终排序结果,361,332,633,589,825,179,664,405,232,457,361,332,232,633,664,825,405,457,589,179,405,825,332,232,633,457,361,664,179,589,基数排序,算法性能分析n：记录数，d：排序码数，r：基数时间复杂度：分配操作：O(n),收集操作O(r)，需进行d趟分配和收集。时间复杂度：O(d(n+r)空间复杂度：所需辅助空间为队首和队尾指针2r个，此外还有为每个记录增加的链域空间n个。空间复杂度O(n+r),36,各排序方法时间复杂度比较,37,各排序方法空间和稳定性比较,38,