第十五章基本排序算法.docx

第十五章基本排序算法一、Python中的排序函数1.（key,reverse）列表自带排序方法，key控制排序的关键字，reverse参数用于控制升降序alist=5,3,4,2,1(reverse=True)print(alist)reverse默认为FalSe(升序)#运行结果15,4,3,2,1alist=(5,9),(3,7),(4,5),(2,8),(1,6)(key=lambdax:xljreverse=True)print(alist)当元素为组合数据类型时，key可以指定排序元素#运行结果（5,9）,（2,8）,（3,7）,（1,6）,（4,5）2.sorted(alist,key,reverse)Python内建函数，排序结果作为函数返回值，不修改alist内容，key,reverse参数功能相同alist=(5,9),(3,7),(4,5),(2,8),(1,6)blist=sorted(alistjkey=lambdax:xljreverse=True)print(blist)参数功能基本相同，主要注意使用方式的不同。3.注意和.values的区别Sort.values(列名,ascending=TrueFalse,inplace=FalseTrue)(DaSCending确定升(True)降(FalSe)序，默认升序(True)(2)inlace声明是否用结果替换原表格，默认False不替换二、冒泡排序1.基本冒泡排序代码defbubble_sort(a):foriinrange(l,len(a):#冒泡轮数forjinrange(len(a)-i):#冒泡方向ifaj>aj+l:#升/降序aj,aj+l=aj+ljajreturnaa=22,13,17,20,14,11print(bubble-sort(a)第一轮冒泡过程冒泡挎序是在一系列数据中，对相邻两个值依次进行比较和调整，让较大的值“下沉（上浮）”，较小的值“上浮（下沉）”的一种排序技术。从第一个值比较到最后一个值的过程称为“一轮”.在一轮排序结束后，最大值（最小值）已经上浮（下沉）到数列的第一个（最后一个）位置。221317201411132217201411131722201411131720221411131720142211131720141122每一轮加工后的结果每轮排序都会将未排序部分的最大值（最小值）已经上浮（下沉）到数列的第一个（最后一个）位置0这个最大值（/小值）将不参与下一轮的比较（或称为“锁定”），经过nT轮排序后，仅剩一个值没有锁定，排序结束。2213172014111317201411221317141120221314111720221311141720221113141720222 .胃泡排序的特性2.1 稳定性【稳定性定义详见17章】冒泡排序是一种稳定的排序算法。故对一组数据进行冒泡排序时，数据交换的次数等于原数据中“逆序对”的个数,与冒泡排序进行的方向无关。2.2 时间复杂度【时间复杂度定义详见17章】对n个元素的数组，用冒泡排序算法进行排序时，共需比较：(n-l)+(n2)+l=1(次)化简后时间复杂度为OS?)3 .冒泡排序的常见考法3.1 给定外层循环和比较值，根据方向和升降序写出内层和判断语句【例】根据己经给出的条件补全冒泡代码条件外层内层比较从前往后，升序foriinrange(l,len(a)ifaaU+l从前往后，降序foriinrange(len(a)J,-l)ifaj_aj-l从后往前，降序foriinrange(len(a)-l)ifa-aU÷l从后往前，升序foriinrange(len(a)-1,0,-1)ifaU_a|j-l3.2 内层或外层循环不充分外层不充分：对n个元素的数列冒泡排序，外层至少需要n-1轮。当外层循环次数不足时,仅能确定“锁定”部分的元素是有序的。内层循环不充分：对n个元素的数列冒泡排序，第一轮所有值都需要参与比较。当内层循环次数不足时，部分元素将始终不参与排序。3.3 其他常见的变式(1)参与排序的元素不是数值类型，例如字符串(2)分组排序，例如奇偶索引分组，奇偶数分组等(3)根据主要关键字和次要关键字排序(4)其他类型4 .冒泡排序优化试将数组a=7,8,0,Ij6,3,9j4,5,2代入基础冒泡代码，观察程序运行结果。会发现在第7轮排序后数组己经有序，但代码需要再执行两轮才能结束。4.1 通过flag标记提前结束循环基本思路：当某一轮排序没有发生元素交换，则说明数组已经有序defbubble-sort(a):foriinrange(l,len(a):flag=TrueIag初始状态forjinrange(len(a)-i):ifaj>aj+l:aj,aj+l=aj+ljajflag=False#发生交换则标记flagifflag:break#若一轮都未发生交换则说明已经有序returnaa=7j8,0j1,6,3,9,4,5,2print(bubble-sort(a)4.2 通过Start标记，一轮“锁定”多个值基本思路：一轮交换中最后一次交换位置前的值一定有序，可以全部“锁定”。defbubble-sort(a):1 =1whilei<=len(a)-l:start=len(a)-lforjinrange(len(a)-l,i-l,-1):ifaj<aj-l:aj,aj-l=aj-l,ajstart=j-l#记录最后一次比较位置i=start+l#比较位置前的值全部锁定returnaa=7j8,0,1,6j3,9,4,5,2print(bubble-sort(a)三、选择排序1 .基本选择排序代码defselection_sort(a):foriinrange(len(a)-l):k=iforjinrange(i+l,len(a):ifak>aj:#升降序k=j#标记极值位置ak,ai=ai,akreturnaa=22,13,17,20,14,11print(selectionsort(a)每轮加工后的结果选择排序的思路是每一轮都从未排序的值中找到最大值(最小值)放到最左边(最右边)，重复n-轮，排序完成。2 .选择排序的特性2.1 稳定性：一般认为选择排序是一种不稳定的算法2.2 时间复杂度：O(M)2.3 选排优化：选排的优化方式一般从提高查找效率或者减少外层循环次数，比如在一轮中同时找多个极值。四、插入排序1.基本插入排序代码五、其他常见的排序算法常见的排序算法还有快速排序、归并排序、堆排序、桶排序等。剩余的这些排序方式同学仅作了解即可，学有余力的同学可以自行到附录部分继续学习。在选择排序算法时，可以根据实际数据自身的特点来选择相应的算法。I免费增值服务介绍，V学科网(https:WWW3网校通合作校还提供学科网高端社群出品的老师请开讲私享直播课等增值服务。V组卷网(https:ZUjU)是学科网旗下智能题库，拥有小初高全学科超千万精品试题，提供智能组卷、拍照选题、作业、考试测评等服务。扫码关注组卷网解锁更多功能扫码关注学科网每日领取免费资源回复"ppt"免费领180套PPT模板回复"天天领券"来抢免费下载券