[高等教育]数据结构课件 7.ppt

第七章 排序 7.1 交换排序 7.4 归并排序 冒泡排序 一. 二路归并排序 快速排序 二. 文件归并排序 7.2 插入排序 7.5 拓扑分类 直接插入排序 对分插入排序 2-路插入排序 希尔排序对 7.3 选择排序 一. 简单选择排序 二. 堆排序 第七章 排 序 排序(sorting)——用某种方法，把元素的无序序列调整为 按某数据项有序序列的过程。 有序表——排序后的表； 无序表——排序前的表。 排序项——用于排序的数据项； 排序码——排序项中的值。 若以主关键字为排序项，排序结果唯一，否则排序结果不唯一。 如果有排序码Ki=Kj，排序前Ki领先于Kj (ij)， 若所采用的排序方法，使得： 排序后仍保持Ki领先Kj——排序方法是稳定的； 排序后可能使Kj领先于Ki ——排序方法不稳定。 内部排序——排序过程全部在内存中进行。 按照排序所采用的策略不同，内部排序可分为多类。 本章讨论交换排序、插入排序、选择排序、归并排序四类排序； 同时介绍拓扑分类及其实现的基本方法. 7.1 交换排序 交换排序——通过交换元素在表中的位置使其有序的排序方法。 一. 冒泡排序(bubble sort) 1. 基本思路 经过多遍比较及交换相邻元素实现排序。 排序过程： 反复扫描待排序表，扫描过程中做： ① 每一趟(扫描无序表一次)扫描将“最大者沉到底” ——依次比较相邻元素并使之有序； ② 每一趟扫描，记录本趟扫描中最后一次发生元素交换的 前一个位置； ③ 记录每一趟扫描是否进行过元素交换； ④ 直到某一趟扫描无元素交换发生，则排序完成。 7.1 交换排序 一. 冒泡排序(bubble sort) 例如，对无序表(49 38 65 97 76 13 27 44)进行冒泡排序 （非递减），过程如下： 7.1 交换排序 一. 冒泡排序(bubble sort) 2. 算法 简单算法语言描述 P164 注意：算法中，F既是一趟扫描有无交换发生的标记， 又是最后一次发生交换的位置记录。 算法分析： 时间复杂度：最坏情况，对无序表扫描 n 趟，每次下 沉一个元素。共进行次比较，复杂度为O(n2) 空间复杂度： in place 动态性能：稳定(在消除逆序过程中没有产生新的逆序)。 思考： ① 算法的C语言描述 ② 该算法扫描过程中，“大者”下沉速度大于“小者”上浮 速度 ；若能加速“上浮”速度，则可提高效率。如何改进？ 7.1 交换排序 二. 快速排序 快速排序(Quick Sort)——冒泡排序的改进。 基本思想：通过一趟排序把待排序表分成前后两部分，其中前一 部分元素的排序码均不大于后一部分元素的排序码； 然后对每部分元素以同样的方法进行排序，直到全表 元素按排序码有序。 关键：如何把待排序表分为符合上述要求的两部分—线性表分割。 1. 线性表分割 设待排序表为L，进行非递减排序，一趟排序的分割过程为： ① 设置指针i、j分别指向线性表的第一个和最后一个元素； ② 选取一个元素L(k)，做 L(k) T ， L(i) L(k) ； ③ 将j逐渐减小，同时逐次比较L(j)与T，直到L(j) T时， 把L(j)移到L(i)位置，即: L(j) L(i) ； 7.1 交换排序 二. 快速排序 1. 线性表分割 ④ 逐渐增大i，同时逐次比较L(i)与T，直到L(i)T时， 则把L(i)移到L(j)的位置上，即L(i) L(j)； ⑤ 反复做③ 、 ④ ，直到i = j为止，此时令L(i)=T。 例如，分割无序表(65 38