第10章排序算法
1 第 10 章 排序算法
s101概述 排序的主要目的是便于以后在已排序的集合中查找检 索某一成员 若干概念 关键字 排序 排序的稳定性 内排序 外排序 多键排序
2 §10.1 概述 • 排序的主要目的是便于以后在已排序的集合中查找检 索某一成员 • 若干概念 – 关键字 – 排序 – 排序的稳定性 – 内排序 – 外排序 – 多键排序
s101概述 排序方法进行分类 插入排序 交换排序 选择排序 归并排序 分配排序
3 §10.1 概述 • 排序方法进行分类 – 插入排序 – 交换排序 – 选择排序 – 归并排序 – 分配排序
s101概述 算法的时间复杂性 通常只考虑键值的比较次数和记录的移动次数 评价排序的另一个主要标准是执行算法所需的附加空
4 §10.1 概述 • 算法的时间复杂性 – 通常只考虑键值的比较次数和记录的移动次数 • 评价排序的另一个主要标准是执行算法所需的附加空 间
§102插入排序 插入排序的基本方法是:每步将一个待排序的记录按 其关键字的大小插到前面已经排序的序列中的适当位 置,直到全部记录插入完毕为止
5 §10.2 插入排序 • 插入排序的基本方法是：每步将一个待排序的记录按 其关键字的大小插到前面已经排序的序列中的适当位 置，直到全部记录插入完毕为止