DS12_排序讲述.ppt

数据结构课程理论部分 学习结束！ 作业—网络教室。 * * * * * 掌握方法 * 掌握方法 * 掌握方法 * * 掌握方法 * 掌握方法 * 掌握方法 * 掌握方法 * 掌握方法 * 掌握方法 * 掌握方法 * 主要内容 排序的基本概念 插入排序 快速排序 选择排序 归并排序 排序：将一个数据元素（记录）的任意序列，重新排列成一个按关键字有序的序列。 设：R1，R2，R3，…，Rn 是n个记录，k1，k2，k3，…，kn 为它们的关键字，排序就是将记录按关键字递增（或递减）的次序排列起来。 常见的排序结果 递 增：ki ki+1 递 减：ki ki+1 非递减：ki ≤ ki+1 非递增：ki ≥ ki+1 排序的基本概念 排序分类 按照排序记录所在的位置分 内部排序：待排序记录存放在计算机随机存储器中（内存）进行的排序过程。 外部排序：待排序记录数量很大，内存无法一次容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 排序的基本概念 排序分类 按照排序依据的原则分 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 基数排序 排序的基本概念 排序分类 按排序所需工作量 简单排序 基数排序 先进排序 排序基本操作 比较两个关键字大小。 将记录从一个位置移动到另一个位置。 排序的基本概念 排序方法的稳定性 稳定的排序方法：设在排序前的序列中记录 Ri 领先于 Rj（即 ij ），且 Ri、Rj 对应的关键字为 Ki、Kj，如果 Ki＝Kj 并且在排序后的序列中 Ri 仍领先于 Rj，称所用方法是稳定的。 不稳定的排序方法：上述情况下，排序后的序列中Rj领先于Ri。 排序的基本概念 待排序列：49,38,65,97,76,13,27,49 排序后: 13,27,38,49,49,65,76,97 — 稳定 排序后: 13,27,38,49,49,65,76,97—不稳定 插入排序法的基本思想 假设：已经存在一个长度为N的有序(从小到大排列)的数据序列，要将一个新的数插入到该序列中，要求插入后的新序列(长度为N+1)仍然保持有序。 算法的关键是要确定新数据插入的合适位置。 对于一个有序序列，从后向前进行比较，若序列中的数大于要插入的数，则将数列中的数向后移动；否则，完成插入操作。 插入排序—直接插入排序 假设待排序的n个记录{R0,R1,…,Rn-1}存放在数组中，插入记录Ri时，记录集合被划分为两个区间[R0，Ri-1 ]和[Ri，Rn-1 ]，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码Ki与Ki-1，Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插入，原位置的记录向后顺移。 插入排序—直接插入排序 i (0) (1) (2) (3) (4) (5) temp [21] 25 49 25* 16 08 25 1 [21 25] 49 25* 16 08 49 2 [21 25 49] 25* 16 08 25* 3 [21 25 25* 49] 16 08 16 4 [16 21 25 25* 49] 08 08 5 [08 16 21 25 25* 49] 插入排序—直接插入排序 基本思想：用折半查找方法确定插入位置的排序。 插入排序—折半插入排序 例 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 … i=8 20 (6 13 30 39 42 70 85 ) 20 s j m i=8 20 (6 13 30 39 42 70 85 ) 20 i=8 20 (6 13 30 39 42 70 85 ) 20 i=8 20 (6 13 30 39 42 70 85 ) 20 i=8 20 (6