河北大学：《数据结构》课程教学资源（PPT教案课件讲稿）第十章 排序

第十章排序 1教学内容 101基本概念 10.2插入排序 10.3交换排序 104选择排序 105二路归并排序 106基数排序 107外排序 2教学目的及要求 (1)领会排序的基本思想和基本概念; (2)理解并掌握插入排序、冒泡排序、快速排序、直接 选择排序、堆排序、归并排序和基数排序的基本思想 步骤、算法及时空效率分析: (3)了解外排序的定义和基本方法

第十章 排序 ⒈教学内容 10.1 基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 二路归并排序 10.6 基数排序 10.7 外排序 ⒉教学目的及要求 ⑴领会排序的基本思想和基本概念； ⑵理解并掌握插入排序、冒泡排序、快速排序、直接 选择排序、堆排序、归并排序和基数排序的基本思想、 步骤、算法及时空效率分析； ⑶了解外排序的定义和基本方法

3、教学重点 (1)排序基本概念及内排序和外排序、稳定排序和非稳 定排序的区别; (2插入排序的基本思想、基本步骤和算法; (3)冒泡排序的基本思想、基本步骤、算法和算法分析 (4快速排序的基本思想、基本步骤和算法; 直接选择排序的基本思想、基本步骤、算法和算法 分析; (6堆排序的基本思想、基本步骤和算法 (7)归并排序的思想; (8)两个有序文件合并的方法和算法 (9)二路归并排序的算法和时空性能 4、教学难点 (1)快速排序算法; (2)堆排序方法

3、教学重点 ⑴排序基本概念及内排序和外排序、稳定排序和非稳 定排序的区别； ⑵插入排序的基本思想、基本步骤和算法； ⑶冒泡排序的基本思想、基本步骤、算法和算法分析； ⑷快速排序的基本思想、基本步骤和算法； ⑸直接选择排序的基本思想、基本步骤、算法和算法 分析； ⑹堆排序的基本思想、基本步骤和算法； ⑺归并排序的思想； ⑻两个有序文件合并的方法和算法； ⑼二路归并排序的算法和时空性能 4、教学难点 ⑴快速排序算法； ⑵堆排序方法

101基本概念 排序( Sorting)是计算机程序设计中的一种重要 操作,其功能是对一个数据元素集合或序列重新排 列成一个按数据元素某个项值有序的序列。作为排 序依据的数据项称为“排序码”,也即数据元素的 关键码。为了便于查找,通常希望计算机中的数据 表是按关键码有序的。如有序表的折半查找,查找 效率较高。还有,二叉排序树、B-树和B+树的构造 过程就是一个排序过程。若关键码是主关键码,则 对于任意待排序序列,经排序后得到的结果是唯一 的;若关键码是次关键码,排序结果可能不唯一, 这是因为具有相同关键码的数据元素,这些元素在 排序结果中,它们之间的的位置关系与排序前不能 保持

10.1 基本概念 排序(Sorting)是计算机程序设计中的一种重要 操作，其功能是对一个数据元素集合或序列重新排 列成一个按数据元素某个项值有序的序列。作为排 序依据的数据项称为“排序码” ，也即数据元素的 关键码。为了便于查找，通常希望计算机中的数据 表是按关键码有序的。如有序表的折半查找，查找 效率较高。还有，二叉排序树、B-树和B+树的构造 过程就是一个排序过程。若关键码是主关键码，则 对于任意待排序序列，经排序后得到的结果是唯一 的；若关键码是次关键码，排序结果可能不唯一， 这是因为具有相同关键码的数据元素，这些元素在 排序结果中，它们之间的的位置关系与排序前不能 保持

若对任意的数据元素序列,使用某个排序方法 对它按关键码进行排序:若相同关键码元素间的位 置关系,排序前与排序后保持一致,称此排序方法 是稳定的;而不能保持一致的排序方法则称为不稳 定的。 排序分为两类:内排序和外排序 内排序:指待排序列完全存放在内存中所进行 的排序过程,适合不太大的元素序列。 外排序:指排序过程中还需访问外存储器,足够 大的元素序列,因不能完全放入内存,只能使用外 排序

若对任意的数据元素序列，使用某个排序方法， 对它按关键码进行排序：若相同关键码元素间的位 置关系，排序前与排序后保持一致，称此排序方法 是稳定的；而不能保持一致的排序方法则称为不稳 定的。 排序分为两类：内排序和外排序。 内排序：指待排序列完全存放在内存中所进行 的排序过程，适合不太大的元素序列。 外排序：指排序过程中还需访问外存储器，足够 大的元素序列，因不能完全放入内存，只能使用外 排序

102插入排序 10.21直接插入排序 设有n个记录,存放在数组r中,重新安排记录在 数组中的存放顺序,使得按关键码有序。即 r[1]. keys[2].keys...<rn]. key 先来看看向有序表中插入一个记录的方法 「;111x 设1<j≤n,r[1] keyer[2]key≤.sr 将r插入,重新安排存放顺序,使得 [1]keys{2]key≤…]key,得到新的有序表 记录数增

10.2 插入排序 10.2.1 直接插入排序 设有n个记录，存放在数组r中，重新安排记录在 数组中的存放顺序，使得按关键码有序。即 r[1].key≤r[2].key≤……≤r[n].key 先来看看向有序表中插入一个记录的方法： 设１<ｊ≤ｎ，r[1].key≤r[2].key≤……≤r[j-1].key， 将 r[j] 插 入 ， 重 新 安 排 存 放 顺 序 ， 使 得 r[1].key≤r[2].key≤……≤r[j].key，得到新的有序表， 记录数增１

【算法101】 ①r0=rjl; ∥r送关r0中,使rj为待插入 记录空位 i=j-1; ∥从第个记录向前测试插入位置 用r0为辅助单元,可兔去测试i1 ⑨若r0 keyer. key,转④。/插入位置确定 ③若r0key< r. key时, r[i+1l=ri;i=-i1;转②。∥调整待插入位置 ④ri+1-r0J;结束。 /放待插入记录

【算法10.1】 ① r[0]=r[j]； //r[j]送r[0]中，使r[j]为待插入 记录空位 i=j-1； //从第i个记录向前测试插入位置， 用r[0]为辅助单元， 可免去测试i<1。 ② 若r[0].key≥r[i].key，转④。 //插入位置确定 ③ 若r[0].key < r[i].key时， r[i+1]=r[i]；i=i-1；转②。 //调整待插入位置 ④ r[i+1]=r[0]；结束。 //存放待插入记录

【例101】向有序表中插入一个记录的过程如下: r{r2]r3r{4r5存储单元 21018259将r5插入四个记录的有序表 中,j r Orll; 初始化,设置待插入位置 2101825 ri+1为待插入位置 i=4,r0<rl,ri+1=rl;i-;调整待插入位置 21018口25 1-3,r0<r,ri+1=rl;r调整待插入位置 2101825 i=2,r0<ri,ri+1=r闻i;i-;调整待插入位置 2口101825 i=1,r0≥r[,ri+1r0;插入位置确定,向空位 填入插入记录 29101825向有序表中插入一个记录的过 程结束

【例10.1】向有序表中插入一个记录的过程如下： r[1] r[2] r[3] r[4] r[5] 存储单元 2 10 18 25 9 将r[5]插入四个记录的有序表 中，j=5 r[0]=r[j]；i=j-1； 初始化，设置待插入位置 2 10 18 25 □ r[i+1]为待插入位置 i=4，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 10 18 □ 25 i=3，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 10 □ 18 25 i=2，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 □ 10 18 25 i=1，r[0] ≥r[i]，r[i+1]=r[0]； 插入位置确定，向空位 填入插入记录 2 9 10 18 25 向有序表中插入一个记录的过 程结束

直接插入排序方法:仅有一个记录的表总是有 序的,因此,对n个记录的表,可从第二个记录开始 直到第n个记录,逐个向有序表中进行插入操作,从 而得到n个记录按关键码有序的表。 【算法10.2】 void InsertSort(S TBL &p) for(i=2: ilength; i++) if(p->elemi]. keyelem i-1.key /小于时,需将eem插入有序表 p>elem0=p->elem[i;为统一算 法设置监测 for(j=i-1: p->elem[]. key p- >elemi key; j--) p>elem+1}=p-> eleme;体记录后移* p->elem+1l=p->elem|0;/插入到正确位置}

直接插入排序方法：仅有一个记录的表总是有 序的，因此，对n个记录的表，可从第二个记录开始 直到第n个记录，逐个向有序表中进行插入操作，从 而得到n个记录按关键码有序的表。 【算法10.2】 void InsertSort(S_TBL &p) { for(i=2；ilength；i++) if(p->elem[i].key elem[i-1].key) /*小于时，需将elem[i]插入有序表*/ { p->elem[0]=p->elem[i]； /*为统一算 法设置监测*/ for(j=i-1 ； p->elem[0].key elem[j].key；j--) p->elem[j+1]=p->elem[j]； /*记录后移*/ p->elem[j+1]=p->elem[0]；/*插入到正确位置*/}}

效率分析】 空间效率:仅用了一个辅助单元。 时间效率:向有序表中逐个插入记录的操作, 进行了n-1趟,每趟操作分为比较关键码和移动记录, 而比较的次数和移动记录的次数取决于待排序列按 关键码的初始排列。 最好情况下:即待排序列已按关键码有序,每 趟操作只需1次比较2次移动 总比较次数=n-1次 总移动次数=2(n-1)次 最坏情况下:即第j趟操作,插入记录需要同前 面的个记录进行j次关键码比较,移动记录的次数为 j+2次

【效率分析】 空间效率：仅用了一个辅助单元。 时间效率：向有序表中逐个插入记录的操作， 进行了n-1趟，每趟操作分为比较关键码和移动记录， 而比较的次数和移动记录的次数取决于待排序列按 关键码的初始排列。 最好情况下：即待排序列已按关键码有序，每 趟操作只需1次比较2次移动。 总比较次数=n-1次 总移动次数=2(n-1)次 最坏情况下：即第j趟操作，插入记录需要同前 面的j个记录进行j次关键码比较，移动记录的次数为 j+2次

总比较次数=∑j=m(n-1) 总移动次数=∑(+2)=m(n-1)+2n 平均情况下:即第趟操作,插入记录大约同前面的 个记录进行关键码比较,移动记录的次数为j/22次 总比较次数=∑ n(n ≈-n 4 4 总移动次数=∑(4+2)=1m-1)+2n=n j=1 由此,直接插入排序的时间复杂度为O(m2)。是一 个稳定的排序方法

( 1) 2 1 1 1 = = − − = j n n n j j n n n n j ( 1) 2 2 1 ( 2) 1 1 = + = − + − = 总比较次数 总移动次数 平均情况下：即第j趟操作，插入记录大约同前面的j/2 个记录进行关键码比较，移动记录的次数为j/2+2次。 总比较次数 总移动次数 2 1 1 4 1 ( 1) 4 1 2 n n n j n j = = −  − = 2 1 1 4 1 ( 1) 2 4 1 2) 2 ( n n n n j n j = + = − +  − = 由此，直接插入排序的时间复杂度为O(n2 )。是一 个稳定的排序方法