第十章排序 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，得到新的有序表， 记录数增１