第十章内部排序 甚本概念 插入排序 快速排序 ·选择排序 归并排序 甚数排序
第十章 内部排序 • 基本概念 • 插入排序 • 快速排序 • 选择排序 • 归并排序 • 基数排序
10.1基本概念 设含有m个记录的文件{R1R2,Rn},其相应的关 键字为{K1,K2,,K},将记录按关键字值非递减(或 非递增)顺序排列的过程,称为排序。 对所有的K=K(,若排序前R领先于R排序后 R仍领先于R1,则称该排序方法是稳定的,反之,称 为不稳定的。 稳定性是对序列中的两个相同的关键字在初始序 列和最终有序序列中相对位置(即领先关系)是否 变化
10.1 基本概念 设含有n个记录的文件{R1,R2,...,Rn}，其相应的关 键字为{K1,K2,...,Kn}，将记录按关键字值非递减(或 非递增)顺序排列的过程，称为排序。 对所有的Ki=Kj (i≠j),若排序前Ri领先于Rj,排序后 Ri仍领先于Rj,则称该排序方法是稳定的，反之，称 为不稳定 的。 稳定性是对序列中的两个相同的关键字在初始序 列和最终有序序列中相对位置（即领先关系）是否 变化
10.1基本概念 内部摊序:待排序文件的全部记录存放在内存 进行的排序,称为内部排序。 外部排序:排序过程中需要进行内外存数据交 换的排序,称为外部排序
10.1 基本概念 内部排序：待排序文件的全部记录存放在内存 进行的排序，称为内部排序。 外部排序：排序过程中需要进行内外存数据交 换的排序，称为外部排序
10.1基本概念 内排序分类 按排序过程依据的原则分为:插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分:简单排序O(n2) 先进排序O(mogm 基数排序O(d.n)
10.1 基本概念 内排序分类 按排序过程依据的原则分为：插入排序 交换排序 选择排序 归并排序 计数排序 按排序过程所需的工作量分：简单排序 O(n2 ) 先进排序 O(nlogn) 基数排序 O(d．n)
102插入排序 直接插入排序(最简单的排序方法) 1.基本思想:依次将每个待排序的记录插入到一个有 序子文件的合适位置(有序子文件记录数增1) 例如:已有待排序文件为:38,65,49,76,97 首先将文件的第一个记录,视为有序文件,然后从第 二个记录开始,直到最后一个记录,依次将他们插 入到有序文件的合适位置
10.2 插入排序 一. 直接插入排序(最简单的排序方法） ⒈ 基本思想：依次将每个待排序的记录插入到一个有 序子文件的合适位置(有序子文件记录数增1) 例如：已有待排序文件为：38，65，49，76，97 首先将文件的第一个记录，视为有序文件，然后从第 二个记录开始，直到最后一个记录，依次将他们插 入到有序文件的合适位置