第0章排序课件.ppt

第10章 排序 排序的基本概念（P200） 排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。 排序的基本概念 排序的分类 1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中 2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 排序的基本概念 排序算法的性能指标 1. 时间开销： ⑴比较：关键码之间的比较； ⑵移动：记录从一个位置移动到另一个位置。 2. 空间开销： 辅助存储空间 3. 算法的稳定性 排序算法的存储结构 从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。 假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用 假定2：将待排序的记录序列排序为升序序列。 10.2 冒泡排序 交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。 冒泡排序的改进。（P202） 冒泡排序的时间性能分析 最好情况（正序）： 比较次数：n-1 移动次数：0 时间复杂度为O(n)。 冒泡排序的时间性能分析 冒泡排序的性能分析 在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。 冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。 冒泡排序是一种稳定的排序方法。 10.3 选择排序 选择排序的主要操作是选择，其主要思想是:每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。 简单选择排序 简单选择排序的主要思想是： 第i 趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。 需解决的关键问题? ⑴如何在待排序序列中选出关键码最小的记录？ ⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置？ 问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 问题2：如何确定最小记录的最终位置？ 解决方法： 第i趟简单选择排序的待排序区间是r[i] ~ r[n]，则r[i]是无序区第一个记录，所以，将index所记载的关键码最小的记录与r[i]交换。 10.4 插入排序 插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。 直接插入排序 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。 直接插入排序 基本思想：在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序。 需解决的关键问题： （1）如何构造初始的有序序列？ （2）如何查找待插入记录的插入位置? 直接插入排序过程示例 问题1：如何构造初始的有序序列 解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。 算法描述：for (i=2; i=n; i++) { 插入第i个记录，即第i趟直接插入排序；} 问题2：如何查找待插入记录的插入位置? 直接插入排序的时间性能分析 直接插入排序的时间性能分析 直接插入排序的性能分析 空间性能：需要一个记录的辅助空间。 直接插入排序算法是一种稳定的排序算法。 直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。 当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。 10.5 希尔排序 对直接插入排序进行改进 改进的着眼点： （1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高； （2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。 基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。 需解决的关键问题? （1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？ （2）子序列内如何进行直接插入排序？