二、第九章排序解析 ■本章课程主要介绍各种排序的定义和相关概念， 排序的算法实现步骤，掌握其中的关键步骤，了 解有关算法的性能和时间复杂度。 www.open.ha.cn v
www.open.ha.cn 二、第九章排序解析 ▪ 本章课程主要介绍各种排序的定义和相关概念， 排序的算法实现步骤，掌握其中的关键步骤，了 解有关算法的性能和时间复杂度
二、第九章排序解析 ·1、直接插入排序 基本思想：整个排序过程为-1趟插入，即先将序 列中第1个记录看成是一个有序子序列，然后从第 2个记录开始，逐个进行插入，直至整个序列有序。 时间复杂度：On2) 空间复杂度：O(1) ■ 排序比较次数：序列正序，最好（n-1) 序列逆序，最差n（n-1)2 稳定性：稳定 www.open.ha.cn
www.open.ha.cn 二、第九章排序解析 ▪ 1、直接插入排序 ▪ 基本思想：整个排序过程为n-1趟插入，即先将序 列中第1个记录看成是一个有序子序列，然后从第 2个记录开始，逐个进行插入，直至整个序列有序。 ▪ 时间复杂度：O(n2) ▪ 空间复杂度：O(1) ▪ 排序比较次数：序列正序，最好（n-1） 序列逆序，最差n（n-1）/2 ▪ 稳定性：稳定
二、第九章排序解析 ■1、直接插入排序 ■什么叫算法的稳定性？ ·稳定性：在待排记录中，任何两个排序码（关键 字)相同的记录，用某种排序方法排序后相对位 置不变，则称这种排序方法是稳定的，否则称为 不稳定的。 ■待排序列：49,38,65,97,76,13,27,49 排序后：13,27,38,49,49,65,76,97一稳定 排序后：13,27,38,49,49,65,76,97一不稳定 www.open.ha.cn ⑦
www.open.ha.cn 二、第九章排序解析 ▪ 1、直接插入排序 ▪ 什么叫算法的稳定性？ ▪ 稳定性：在待排记录中，任何两个排序码（关键 字）相同的记录，用某种排序方法排序后相对位 置不变，则称这种排序方法是稳定的，否则称为 不稳定的。 ▪ 待排序列：49,38,65,97,76,13,27,49 排序后:13,27,38,49,49,65,76,97 — 稳定 排序后:13,27,38,49,49,65,76,97 — 不稳定
二、 第九章排序解析 ·1、直接插入排序 i=1(49)386597761327 i=238(3849)65.97761327 i=365(384965)97761327 i=497(38496597)'761327 i=576(38496576$7)1327 i=613(133849657697)27 i=72713,32793849(6576 97) 排序结果：13j27j3849657697)j www.open.ha.cn
www.open.ha.cn 二、第九章排序解析 ▪ 1、直接插入排序 i=1 （49） 38 65 97 76 13 27 i=2 38 （38 49） 65 97 76 13 27 i=3 65 （38 49 65） 97 76 13 27 i=4 97 （38 49 65 97） 76 13 27 i=5 76 （38 49 65 76 97） 13 27 i=6 13 （13 38 49 65 76 97） 27 i=7 27（13 38 49 65 76 97） 27 j j j j j j 27 38 49 65 76 97） 排序结果：（13 27 38 49 65 76 97）
二、第九章排序解析 ■2、 折半插入排序 基本思想：是在直接插入排序的基础上改进的一 种算法。在一个有序序列中插入一个新的记录， 则可以利用"折半查找"查询插入位置。 时间复杂度：0(n2) 空间复杂度：0(1) ■稳定性：稳定 www.open.ha.cn
www.open.ha.cn 二、第九章排序解析 ▪ 2、折半插入排序 ▪ 基本思想：是在直接插入排序的基础上改进的一 种算法。在一个有序序列中插入一个新的记录， 则可以利用"折半查找"查询插入位置 。 ▪ 时间复杂度：O(n2) ▪ 空间复杂度：O(1) ▪ 稳定性：稳定
二、第九章排序解析 ■ 2、折半插入排序 i=1(30)137085 3942620 i=213(1330)708539 42620 i=820(613 3039 4270 85)20 5=0 m=3 j=6 i=820(6,1330 394270 85)20 5=0m=1j=2 i=820(61330 39 427085)20 sm s=2,j=2m=2 i=820(6 1330 39 427085)20 i,m [s s=2>j=m-1=1,找到位置，j后的记录后移，记录插入)+1位置 i=820(613203039427085) www.open.ha.cn
www.open.ha.cn 二、第九章排序解析 ▪ 2、折半插入排序 i=1 (30) 13 70 85 39 42 6 20 i=2 … 13 (13 30) 70 85 39 42 6 20 i=8 20 (6 13 30 39 42 70 85 ) 20 s=0 m=3 j=6 i=8 20 (6 13 30 39 42 70 85 ) 20 s=0 m=1 j=2 i=8 20 (6 13 30 39 42 70 85 ) 20 j,m s i=8 20 (6 13 20 30 39 42 70 85 ) i=8 20 (6 13 30 39 42 70 85 ) 20 smj s=2，j=2 m=2 s=2 > j=m-1=1，找到位置，j后的记录后移，记录插入j+1位置
二、第九章排序解析 ·3、冒泡排序 ■ 基本思想：顺序比较相邻的两记录的关键字，小 的元素逐渐上移，大的元素则逐渐下移。每一趟 找到一个最小值。重复上述过程，直到“在一趟 排序过程中没有进行过交换记录的操作”为止。 时间复杂度：0(n2) 空间复杂度：0(1) ·稳定性：稳定 www.open.ha.cn 6
www.open.ha.cn 二、第九章排序解析 ▪ 3、冒泡排序 ▪ 基本思想：顺序比较相邻的两记录的关键字，小 的元素逐渐上移，大的元素则逐渐下移。每一趟 找到一个最小值。重复上述过程，直到“在一趟 排序过程中没有进行过交换记录的操作”为止。 ▪ 时间复杂度：O(n2) ▪ 空间复杂度：O(1) ▪ 稳定性：稳定
二、 第九章排序解析 ·3、冒泡排序 最好情况：有序，比较n-1次 ·最坏情况：逆序，比较(n2-n)/2次 33 09 09 09 09 26 33 26 26 26 86 26 33 30 30 09 86 30 33 33 45 30 86 45 45 30 45 45 86 86 原始 第一次第二次第三次第四次 www.open.ha.cn
www.open.ha.cn 二、第九章排序解析 ▪ 3、冒泡排序 ▪ 最好情况：有序，比较n-1次 ▪ 最坏情况：逆序，比较(n2-n)/2次 33 09 09 09 09 26 33 26 26 26 86 26 33 30 30 09 86 30 33 33 45 30 86 45 45 30 45 45 86 86 原始 第一次 第二次 第三次 第四次
二、第九章排序解析 ■4、快速排序 ■ 基本思想：任取待排序对象序列中的某个对象 (例如取第一个对象)作为基准，按照该对象的关 键码大小，将整个对象序列划分为左右两个子序 左侧子序列中所有对象的关键码都小于或等于基 准对象的关键码。 ■ 右侧子序列中所有对象的关键码都大于基准对象 的关键码。 然后分别对这两个子序列重复施行上述方法，直 到所有的对象都排在相应位置上为止。 www.open.ha.cn ⑦
www.open.ha.cn 二、第九章排序解析 ▪ 4、快速排序 ▪ 基本思想：任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准，按照该对象的关 键码大小，将整个对象序列划分为左右两个子序 列 ▪ 左侧子序列中所有对象的关键码都小于或等于基 准对象的关键码。 ▪ 右侧子序列中所有对象的关键码都大于基准对象 的关键码。 ▪ 然后分别对这两个子序列重复施行上述方法，直 到所有的对象都排在相应位置上为止
二、 第九章排序解析 ■4、 快速排序 时间复杂度：0(nlog2n) 空间复杂度：O(og2n),因为递归要用堆栈。 稳定性：不稳定 快速排序实例 www.open.ha.cn 6
www.open.ha.cn 二、第九章排序解析 ▪ 4、快速排序 ▪ 时间复杂度：O(nlog2n) ▪ 空间复杂度：O(log2n)，因为递归要用堆栈。 ▪ 稳定性：不稳定 ▪ 快速排序实例