算法分析 >稳定性:稳定的 时间复杂度:O(n2) ●最快的情况:正序 最慢的情况:逆序
➢ 稳定性: 稳定的 ➢ 时间复杂度:Ｏ(n2 ) • 最快的情况：正序 • 最慢的情况：逆序 三. 算法分析
46交换排序 交换排序是通过对数据表中的记 录进行两两比较,次序不符合要求就 交换的方法实现数据表的有序排列 目前有两种较为常用的交换排序 方法:冒泡排序和快速排序。本节重 点介绍其中的冒泡排序方法
4.6 交换排序 交换排序是通过对数据表中的记 录进行两两比较，次序不符合要求就 交换的方法实现数据表的有序排列。 目前有两种较为常用的交换排序 方法：冒泡排序和快速排序。本节重 点介绍其中的冒泡排序方法
4.6.1冒泡排序
计 算 机 软 件 基 础 一． 基本思想 将待排序的n个记录看作按纵向排列，每趟排 序时自下至上对排序范围中每对相邻记录进行比较 ，若次序不符合要求（逆序）就交换。每趟排序结 束时都能使排序范围内关键字最小的记录象气泡一 样“冒”（上升）到表上端的对应位置。重复此过 程，依次将关键字最小、次小、第三小…的各个记 录“冒”到表上端的第一个、第二个、第三个、… 位置上，直至整个表有序排列。 4.6.1 冒泡排序
例1:对关键字序列{91,38,20,46,38,74,12} 进行冒泡排序,写出排序过程中每趟排序的结果 注:在关键字序列中存在两个相同的关键字38, 因此在后面一个38的下面加下划线以示区别。注意 通过此实例分析排序方法的稳定性
计 算 机 软 件 基 础 • 注：在关键字序列中存在两个相同的关键字38， 因此在后面一个38的下面加下划线以示区别。注意 通过此实例分析排序方法的稳定性. 例1：对关键字序列{91 ，38，20，46，38，74，12} 进行冒泡排序，写出排序过程中每趟排序的结果
冒泡排序示例一以升序为例 n~2趟n-3趟n-4趟n~5趟n-6趟n7尚 12 12 12 12 12 12 12 20 20 20 20 20 38 91 38 38 38 38 38 91 38 38 38 12 38 38 91 46 38 46 46 46 91 74 74 74 4 74 74 91
冒泡排序示例----以升序为例 第一趟 91 38 20 46 38 74 12 i 12 20 12 91 12 74 12 38 46 38 12 12 12 12 74 38 46 20 38 91 12 74 3846 38 2038 i 20 2091 38 第二趟 第三趟 12 74 46 38 20 91 38 第四趟 12 74 46 91 20 38 38 第五趟 12 74 91 46 20 38 38 第六趟 12 91 74 46 20 38 n~2 n~3 n~4 n~5 n~6 n~7