15.基本排序算法 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十五章 基本排序算法 一、Python中的排序函数 1.alist.sort(key,reverse) 列表自带排序方法，key控制排序的关键字，reverse参数用于控制升降序 alist = [5,3,4,2,1] alist.sort(reverse=True) print(alist) reverse 默认为False(升序) #运行结果 [5, 4, 3, 2, 1] alist = [(5,9),(3,7),(4,5),(2,8),(1,6)] alist.sort(key=lambda x:x[1],reverse=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(alist,key=lambda x:x[1],reverse=True) print(blist) 参数功能基本相同，主要注意使用方式的不同。 3.注意和dataframe.sort_values的区别 sort_values(列名,ascending=True/False,inplace=False/True) (1)ascending确定升（True）降(False)序，默认升序（True） (2)inplace声明是否用结果替换原表格，默认False不替换 二、冒泡排序 1.基本冒泡排序代码 def bubble_sort(a):     for i in range(1,len(a)): #冒泡轮数         for j in range(len(a)-i): #冒泡方向             if a[j]>a[j+1]: #升/降序                 a[j],a[j+1]=a[j+1],a[j] return a a = [22,13,17,20,14,11] print(bubble_sort(a)) 第一轮冒泡过程 冒泡排序是在一系列数据中，对相邻两个值依次进行比较和调整，让较大的值“下沉（上浮）”，较小的值“上浮（下沉）”的一种排序技术。 从第一个值比较到最后一个值的过程称为“一轮”。在一轮排序结束后，最大值（最小值）已经上浮（下沉）到数列的第一个（最后一个）位置。 每一轮加工后的结果 每一轮排序都会将未排序部分的最大值（最小值）已经上浮（下沉）到数列的第一个（最后一个）位置。这个最大值（最小值）将不参与下一轮的比较（或称为“锁定”），经过n-1轮排序后，仅剩一个值没有锁定，排序结束。 2.冒泡排序的特性 2.1稳定性【稳定性定义详见17章】 冒泡排序是一种稳定的排序算法。故对一组数据进行冒泡排序时，数据交换的次数等于原数据中“逆序对”的个数，与冒泡排序进行的方向无关。 2.2时间复杂度【时间复杂度定义详见17章】 对n个元素的数组，用冒泡排序算法进行排序时，共需比较： （次） 化简后时间复杂度为O(n2) 3.冒泡排序的常见考法 3.1给定外层循环和比较值，根据方向和升降序写出内层和判断语句 【例】根据已经给出的条件补全冒泡代码 条件 外层 内层 比较 从前往后，升序 for i in range(1,len(a)) if a[j] ___ a[j+1] 从前往后，降序 for i in range(len(a),1,-1) if a[j] ___ a[j-1] 从后往前，降序 for i in range(len(a)-1) if a[j] ___ a[j+1] 从后往前，升序 for i in range(len(a)-1,0,-1) if a[j] ___ a[j-1] 3.2内层或外层循环不充分 外层不充分：对n个元素的数列冒泡排序，外层至少需要n-1轮。当外层循环次数不足时，仅能确定“锁定”部分的元素是有序的。 内层循环不充分：对n个元素的数列冒泡排序，第一轮所有值都需要参与比较。当内层循环次数不足时，部分元素将始终不参与排序。 3.3其他常见的变式 (1)参与排序的元素不是数值类型，例如字符串 (2)分组排序，例如奇偶索引分组，奇偶数分组等 (3)根据主要关键字和次要关键字排序 (4)其他类型 4.冒泡排序优化 试将数组a=[7, 8, 0, 1, 6, 3