计算机应用基础16排序.pptx

,是计算机程序设计中一个重要运算,它的功能是将一组任意序列的数据元素,进行按关键字由大到小的顺序(降序)排列或按由小到大的顺序(升序)排列。排序的对象:这些数据元素可以是数值型,也可以为字符型。若为数值型,则按数值大小排列;若为字符型,则按其ASCII码的顺序排列。排序的依据:在实际应用中,参加排序的数据元素有时不是单个数据项,而是由多个数据项组成的记录。此时排序应按照关键字的大小进行。所谓关键字是指记录中的某个数据项,用它可以标识一个记录。若此关键字可以唯一地标识一个记录,则称此关键字为主关键字;反之,把用以识别若干记录的关键字称为次关键字。学号姓名系别住址电话981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎5372221文档分享排序的稳定性:在待排序的记录中,若存在多个关键在相同的记录,经过排序后,这些具有相同关键在的记录之间的相对次序发生变化,则称这种排序方法是稳定的;否则,是不稳定的。排序的分类:内部排序与外部排序内部排序::由于待排序记录数据量太大,内存无法容纳全部数据,:算法执行时间(最好、最差及平均情况)、::认可第1个记录已排好序,然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。:折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。:,逐个按其排序码值的大小插入到已排好序的若干个记录组成的文件中的适当位置,保持新文件有序。:思路:认可第1个记录已排好序,然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中)将Ri的排序码与前面已排好序的排序码从右向左依次比较,找到Ri应插入的位置;将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。<例>直接插入排序:次数ir[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8](49)39669676113750(3949)669676113750i=239(394966)9676113750i=366(39496696)76113750i=496(3949667696)113750i=576(1**********)3750i=611(11373949667696)50i=737(1137394950667696)i=850对于有n个数据元素的待排序列,插入操作要进行n-1次文档分享............./*对N个整数进行升序排序*/for(i=1;i<N;i++){for(k=i-1;k>=0;k--)//寻找插入位置 if(a[i]>a[k]) break;//插入到第k个位置的后面temp=a[i];for(j=i-1;j>k;j--)//向后移动 a[j+1]=a[j];a[j+1]=temp;}文档分享............./*改进前面的算法*/for(i=1;i<N;i++){/*一边比较,一边移动*/temp=a[i];for(j=i-1;j>=0&&temp<a[j];j--)a[j+1]=a[j];a[j+1]=temp;}temp>a[j]若降序排序,则::时效分析最好情况:初始排序码已经有序。共比较n-1次,移动0次。最坏情况:待排序序列完全逆序。比较和移动均为n(n-1)/2次。平均情况:比较和移动次数均约为n2/4,时间复杂度为O(n2)。,时间复杂度为O(n2).文档分享2、折半插入排序折半插入排序在寻找插入位置时,不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多,改进效果越明显。例:有6个记录,前5个已排序的基础上,对第6个记录排序。[1527365369]42lowmidhigh(42>36,后半)[1527365369]42lowhighmid(42<53,前半)[1527365369]42highlow(high<low,查找结束,插入位置