第10章排序 提纲 CONTENTS 10.6基数排序 10.1排序的基本概念 10.7各种内排序方法的比 10.2插入排序 较和选择 10.3交换排序 10.8外排序 10.4选择排序 作业 10.5归并排序 上机实验题 1/69
CONTENTS 提纲 1/69
排序的基本概念10.11.什么是排序所谓排序，就是要整理表中的元素，使之按关键字递增或递减有序排列，本章仅讨论递增排序的情况，在默认情况下所有的排序均指递增排序。排序的输入输出如下：输入：n个元素序列为Re、R1、…、Rn-1，其相应的关键字分别为kg、k1、.…、kn-10输出：Rio，Ri，,Rin-1，使得kio≤kii≤.≤kin-1。2/69
1. 什么是排序 所谓排序，就是要整理表中的元素，使之按关键字递增或递减有序排 列，本章仅讨论递增排序的情况，在默认情况下所有的排序均指递增排 序。排序的输入输出如下： 输入：n个元素序列为R0、R1、.、Rn-1，其相应的关键字分别 为k0、k1、.、kn-1。 输出：Ri0，Ri1，.，Rin-1 ，使得ki0≤ki1≤.≤kin-1。 2/69
2.内排序和外排序在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序，反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。3/69
在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的 内、外存交换，则称之为内排序。 反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。 2. 内排序和外排序 3/69
3.内排序的分类插入排序交换排序基于比较的排序选择排序归并排序内排序基数排序不基于比较的排序.4/69
内排序 3. 内排序的分类 基于比较的排序 不基于比较的排序 插入排序 交换排序 选择排序 归并排序 基数排序 4/69
基于比较的排序算法的性能基于比较的排序算法中，主要进行以下两种基本操作：比较：元素关键字之间的比较。移动：元素从一个位置移动到另一个位置。5/69
4. 基于比较的排序算法的性能 基于比较的排序算法中，主要进行以下两种基本操作： 比较：元素关键字之间的比较。 移动：元素从一个位置移动到另一个位置。 5/69