数据结构(第9章)资料.ppt

第九章 排序; 3、教学重点 ⑴排序基本概念及内排序和外排序、稳定排序和非稳 定排序的区别； ⑵插入排序的基本思想、基本步骤和算法； ⑶冒泡排序的基本思想、基本步骤、算法和算法分析； ⑷快速排序的基本思想、基本步骤和算法； ⑸直接选择排序的基本思想、基本步骤、算法和算法 分析； ⑹堆排序的基本思想、基本步骤和算法； ⑺归并排序的思想； ⑻两个有序文件合并的方法和算法； ⑼二路归并排序的算法和时空性能 4、教学难点 ⑴快速排序算法； ⑵堆排序方法; 10.1 基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有???表的折半查找，查找效率较高。二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。; 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 排序分为两类：内排序和外排序。 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。;10.2 插入排序;【算法10.1】 ① r[0]=r[j]； //r[j]送r[0]中，使r[j]为待插入记录空位 i=j-1； //从第i个记录向前测试插入位置，用r[0]为辅助单元， 可免去测试i1。 ② 若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]；结束。 //存放待插入记录 ;【例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个记录按关键码有序的表。 ;【效率分析】 空间效率：仅用了一个辅助单元。 时间效率：向有序表中逐个插入记录的操作，进行了n-1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。 最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较2次移动。 总比较次数=n-1次 总移动次数=2(n-