5.2冒泡和选择排序算法及分析（Python进阶-数据结构与算法）课件

冒泡排序和选择排序算法及分析 数据结构与算法（Python版） ❖ 冒泡排序的算法思路在于对无序表进行多 趟比较交换， ❖ 每趟包括了多次两两相邻比较 ， 并将逆序 的数据项互换位置 ， 最终能将本趟的最大 项就位 ❖ 经过n-1趟比较交换 ， 实现整表排序 ❖ 每趟的过程类似于“气泡 ”在水中不断上 浮到水面的经过 数据结构与算法（Python版） 排序：冒泡排序Bubble Sort 0 ❖ 第1趟比较交换 ， 共有n-1对相邻数据进行 比较 一旦经过最大项，则最大项会一路交换到达最后 一项 ❖ 第2趟比较交换时 ， 最大项已经就位 ， 需 要排序的数据减少为 n - 1 ， 共有 n -2对相 邻数据进行比较 ❖ 直到第n- 1趟完成后 ， 最小项一定在列表 首位 ， 就无需再处理了。 数据结构与算法（Python版） 排序：冒泡排序Bubble Sort 0 0 数据结构与算法（Python版） 冒泡排序：第1趟 n-1趟 序错，交换 支持直接交换 alist[i],alist[i+1]=alist[i+1],alist[i] 数据结构与算法（Python版） https://zh.visualgo.net/sorting 冒泡排序：代码 0 Python ❖ 无序表初始数据项的排列状况对冒泡排序 没有影响 ❖ 算法过程总需要n- 1趟 ， 随着趟数的增加 , 比对次数逐步从n-1减少到1 ， 并包括可 能发生的数据项交换。 ❖ 比对次数是1～n-1的累加： 数据结构与算法（Python版） ❖ 比对的时间复杂度是O(n2) 冒泡排序：算法分析 0 ❖ 关于交换次数 ， 时间复杂度也是O(n2) ， 通常每次交换包括3次赋值 ❖ 最好的情况是列表在排序前已经有序 ， 交 换次数为0 ❖ 最差的情况是每次比对都要进行交换 ， 交 换次数等于比对次数 ❖ 平均情况则是最差情况的一半 数据结构与算法（Python版） 冒泡排序：算法分析 0 ❖ 冒泡排序通常作为时间效率较差的排序算 法 ， 来作为其它算法的对比基准。 ❖ 其效率主要差在每个数据项在找到其最终 位置之前， ❖ 必须要经过多次比对和交换 ， 其中大部分 的操作是无效的。 ❖ 但有一点优势 ， 就是无需任何额外的存储 空间开销。 数据结构与算法（Python版） 冒泡排序：算法分析 0 ❖ 另外 ， 通过监测每趟比对是否发生过交换 , 可以提前确定排序是否完成 ❖ 这也是其它多数排序算法无法做到的 ❖ 如果某趟比对没有发生任何交换 ， 说明列 表已经排好序 ， 可以提前结束算法 数据结构与算法（Python版） 冒泡排序：性能改进 0 数据结构与算法（Python版） 冒泡排序：性能改进 0 ❖ 选择排序对冒泡排序进行了改进 ， 保留了 其基本的多趟比对思路 ， 每趟都使当前最 大项就位。 泡排序进行多次交换 ， 每趟仅进行1次交 换 ， 记录最大项的所在位置 ， 最后再跟本 趟最后一项交换 ❖ 选择排序的时间复杂度比冒泡排序稍优 比对次数不变，还是O(n2) 交换次数则减少为O(n) n o h t y P ❖ 但选择排序对交换进行了削减 ， 相比起冒 选择排序Selection Sort 0 数据结构与算法( 版） 数据结构与算法（Python版） 0 数据结构与算法（Python版） 选择排序：代码 0 $$