山东理工大学：《数据结构》课程教学课件（数学）CH10 排序

第十章 非序

10.1概述 10.2插入排序 10.3快速排序 10.4选择排序 10.5归并排序 10.6基数排序 10.7各种排序方法的综合比较

10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种排序方法的综合比较

10.1 概述 一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

10.1 概 述 一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

一、什么是排序？ 排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。 例如：将下列关键字序列 52,49,80,36,14,58,61,23,97,75 调整为 1423,36,49,52,58,61,75,80,97

一、什么是排序？ 排序是计算机内经常进行的一种操作， 其目的是将一组“无序”的记录序列调 整为“有序”的记录序列。 例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97

二、内部排序和外部排序 若整个排序过程不需要访问外存便能 完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序

二、内部排序和外部排序 若整个排序过程不需要访问外存便能 完成，则称此类排序问题为内部排序； 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序

三、内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 有序序列区 无序序列区 经过一趟排序 有序序列区 无序序列区

三、内部排序的方法 内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。 经过一趟排序 有序序列区 无 序 序 列 区 有序序列区 无 序 序 列 区

内部排序方法分类： 基于不同的扩大”有序序列长度的 方法，内部排序大致可分下列几种类型： 插入类 选择类」 交换类 归并类 其它方法 按照排序过程所需要的工作量来分类： 简单排序：0（n2) 先进排序：O(n log n) 基数排序：O（d*n)

内部排序方法分类： 基于不同的“扩大” 有序序列长度的 方法，内部排序大致可分下列几种类型： 插入类 选择类 交换类 归并类 其它方法 按照排序过程所需要的工作量来分类： 简单排序：O（n 2） 先进排序：O（n log n） 基数排序：O（d * n）

设有8个待排序记录，其关键字分别为： 49,38,65,97,76,13,27,49: 对以上关键字分别进行： !直接插入排序 !表插入排序 1折半插入排序 1希尔排序(d:5,2,1) 1起泡排序 ,快速排序 1简单选择排序 1堆排序 2-路归并排序

设有8个待排序记录，其关键字分别为： 对以上关键字分别进行： l 直接插入排序 l 折半插入排序 l 希尔排序(d:5, 2, 1) l 起泡排序 l 快速排序 l 简单选择排序 l 堆排序 l 2-路归并排序 l 表插入排序

1.插入类 将无序子序列中的一个或几个记录 插入到有序序列中，从而增加记录 的有序子序列的长度。 2.选择类 从记录的无序子序列中选择”关 键字最小或最大的记录，并将它加入 到有序子序列中，以此方法增加记录 的有序子序列的长度

1. 插入类 将无序子序列中的一个或几个记录 “插入”到有序序列中，从而增加记录 的有序子序列的长度。 2. 选择类 从记录的无序子序列中“选择”关 键字最小或最大的记录，并将它加入 到有序子序列中，以此方法增加记录 的有序子序列的长度

3.交换类 通过“交换”无序序列中的记录从而 得到其中关键字最小或最大的记录，并将 它加入到有序子序列中，以此方法增加记 录的有序子序列的长度。 4.归并类 通过“归并”两个或两个以上的记录 有序子序列，逐步增加记录有序序列的 长度

3. 交换类 通过“交换”无序序列中的记录从而 得到其中关键字最小或最大的记录，并将 它加入到有序子序列中，以此方法增加记 录的有序子序列的长度。 4. 归并类 通过“归并”两个或两个以上的记录 有序子序列，逐步增加记录有序序列的 长度