14.插入排序与选择排序.ppt

排序 排序的基本概念直接插入排序直接选择排序 排序基本概念 定义排序是将无序的记录序列调整为有序记录序列的一种操作 例如 将下列记录序列 52 49 80 36 14 58 61 23 97 75 调整为序列 14 23 36 49 52 58 61 75 80 97 关键字 key 假定被排序的数据是由一组记录组成的表 而记录则由若干个数据项组成 其中有一项可用来标识一个记录 称为关键字项 该数据项的值称为关键字 关键字可用作排序算法的依据 也称为排序码 排序分类 按待排序记录所在位置内部排序 待排序记录存放在内存外部排序 排序过程中需对外存进行访问的排序按排序依据原则插入排序 直接插入排序 折半插入排序 希尔排序交换排序 冒泡排序 快速排序选择排序 简单选择排序 堆排序归并排序 2 路归并排序基数排序 排序算法的稳定性 假定在待排序的记录集中 存在多个具有相同键值的记录 若经过排序 这些记录的相对次序仍然保持不变 即在原序列中 ki kj且ri在rj之前 而在排序后的序列中 ri仍在rj之前 则称这种排序算法是稳定的 否则称为不稳定的 排序算法的性能指标1 时间开销 比较 关键码之间的比较 移动 记录从一个位置移动到另一个位置 2 空间开销 辅助存储空间3 算法的稳定性 内排序 定义待排记录存放在随机存储器中进行 内存 排序对象针对关键字 排序码 的序列排序算法缺省以顺序表为存储结构非递减有序我们后面讲的插入排序 交换排序 选择排序 归并排序等都是指的内排序 我们从以下几方面来学习每一种排序方法 思想实现时间性能空间性能稳定性适用情况 插入排序 插入排序的基本思想是 将待排序表看做是左 右两部分 其中左边为有序区 右边为无序区 整个排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中 以构成新的有序区 直到全部记录都排好序 三种插入排序方法 直接插入排序 二分法插入排序 也叫折半插入排序 和希尔排序 直接插入排序 基本思想 将数据元素集合分成两部分 一部分为有序区 一部分为无序区 每次从无序区中取出一个数据元素 按其关键字大小将其插入到有序区的适当位置上 直到全部数据元素都插入到有序区中为止 需解决的关键问题 1 如何构造初始的有序序列 2 如何查找待插入记录的插入位置 直接插入排序 要点 把元素集合划分为有序区和无序区初始时 第一个元素默认构成有序区每趟排序过程中 将无序序列的第一个元素插入到有序序列的适当位置 以达到扩大有序区长度的目的 查找的方向 将待插入元素对有序区按照从后向前的顺序比较查找其插入位置 查找的标准 对有序区从后向前查找第一个不大于待插入元素的记录位置 即在查找插入位置过程中 若待插入元素小于当前有序区元素 则将当前有序区元素后移 49386597761327 i 1 3849 6597761327 i 2 384965 97761327 i 3 38496597 761327 i 4 3849657697 1327 i 5 133849657697 27 初始 i 6 133849657697 27 27 13 76 97 65 38 97 76 65 49 38 27 直接插入排序执行过程 直接插入排序flash演示 voidInsertSort DataTypeL intlen inti j DataTypetmp for i 1 i 0 j 有序表数据比较和移动 if tmp key L j key 关键字比较L j 1 L j 记录移动elsebreak L j 1 tmp 插入位置为j 1 structRecord intdata1 intdata2 intkey typedefRecordDataType 划分为两个表 i 1 有序表 L 0 L i 1 第i次排序前 无序表 L i L len 1 第i次排序前 两个循环大循环for i 1 i 0 j 有序表排序新元素L i 插入在j 1位置上j的起始位置是i 1 终止位置为 1或第一个符合tmp key L j key的位置 直接插入排序性能分析 排序中的两个基本操作是 关键字间的 比较和 记录的 移动 排序的时间性能取决于排序过程中这两个操作的次数 直接插入排序这两个操作的次数操作次数取决于待排记录序列的状态 当待排记录处于 正序 的情况时 所需进行的关键字比较和记录移动的次数最少 当待排记录处于 逆序 的情况时 所需进行的关键字比较和记录移动的次数最多 算法评价时间复杂度 T n O n 空间复杂度 S n O 1 只使用i j和tmp3个辅助变量 与问题规模n无关 直接插入排序算法是一种稳定的排序算法 直接插入排序算法简单 容易实现 适用于待排序记录基本有序或待排序记录较少时 当待排序的记录个数较多时 大量的比较和移动操作使直接插入排序算法的效率降低 其它类型插入排序 二分法插入排序 希尔排序 二分法插入排序和希尔排序的算法实现请参照课本 直接选择排序 基本思想 将数据元素序列分成有序区和无序区两部分 每趟排序都从无序区中选取出关键字最小的数据元素放在有序区的最后 直到全部数据元素排序完毕 要点 把元素集合划分为有序区和无序区初始时 有序区为空每趟排序过程中 从无序区中选出关键字最小的数据元素与无序区的第一个元素交换 以达到扩大有序区长度的目的 初始 49386597761327 一趟 13 386597764927 二趟 1327 6597764938 三趟 132738 97764965 四趟 13273849 769765 五趟 1327384965 9776 六趟 132738496576 97 直接选择排序flash演示 voidSelectSort DataTypeL intlen inti j min DataTypetmp 临时变量 用于元素交换for i 0 i len 1 i i 1为排序次数min i for j i 1 j len j 查找最小元素if L j key L min key min j if min i tmp L i L i L min L min tmp 划分为两个表 i 0 有序表 L 0 L i 第i 1次排序后 无序表 L i 1 L len 1 第i 1次排序后 两个循环大循环for i 0 i len 1 i 确定比较的新元素L i min i小循环for j i 1 j len j 确定当前的最小值排序前无序表最小值下标为min 直接选择排序性能分析 直接选择排序比较和移动的次数无论记录序列的初始状态如何 比较次数均相同 移动次数取决于待排记录序列的状态 当待排记录处于 正序 的情况时 所需进行的记录移动的次数最少 当待排记录处于 逆序 的情况时 所需进行的记录移动的次数最多 算法评价时间复杂度 T n O n 空间复杂度 S n O 1 只使用i j k和tmp4个辅助变量 与问题规模n无关 直接选择排序算法是一种不稳定的排序算法 直接选择排序算法简单 容易实现 适用于从大量记录中选择一部分排序 已知一组数据的排序码为 265 301 751 129 937