河池学院：《数据结构》课程电子教案（PPT教学课件）第10章 排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序

第10章排序 提纲 CONTENTS 10.6基数排序 10.1排序的基本概念 10.7各种内排序方法的比 10.2插入排序 较和选择 10.3交换排序 10.8外排序 10.4选择排序 作业 10.5归并排序 上机实验题 1/69

CONTENTS 提纲 1/69

1. 什么是排序 所谓排序，就是要整理表中的元素，使之按关键字递增或递减有序排 列，本章仅讨论递增排序的情况，在默认情况下所有的排序均指递增排 序。排序的输入输出如下： 输入：n个元素序列为R0、R1、.、Rn-1，其相应的关键字分别 为k0、k1、.、kn-1。 输出：Ri0，Ri1，.，Rin-1 ，使得ki0≤ki1≤.≤kin-1。 2/69

在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的 内、外存交换，则称之为内排序。 反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。 2. 内排序和外排序 3/69

内排序 3. 内排序的分类 基于比较的排序 不基于比较的排序 插入排序 交换排序 选择排序 归并排序 基数排序 4/69

4. 基于比较的排序算法的性能 基于比较的排序算法中，主要进行以下两种基本操作： 比较：元素关键字之间的比较。 移动：元素从一个位置移动到另一个位置。 5/69

排序算法的性能由算法的时间和空间确定的，而时间又是由比较 和移动的次数确定的。 若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素 为正序。 反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表 中元素为反序。 6/69

(R3,R1,R2) (R3,R2,R1) (R2,R3,R1) (R2,R1,R3) (R1,R3,R2) 是 否 (R1,R2,R3) k1≤k2 k2≤k3 ① k1≤k3 ② ③ 是 否 是 否 k1≤k3 ④ k2≤k3 ⑤ ⑥ 是 否 (R1,R2,R3) (R1,R2,R3) (R1,R3,R2) (R2,R1,R3) (R2,R3,R1) n=3的决策树 正序不变，逆序交换！ 3!=6个叶子结点 7/69

推广一下，对于n个元素排序结果有n!种情况，对应的决策树是一棵有n! 个叶子结点的二叉树。 设其高度为h，其中没有单分支结点，总结点个数=2n!-1，其高度等同于 含2n!-1个结点的完全二叉树的高度，则h=log2(2n!)= log2n!+1，而 log2n!≈nlog2n，即h=O(nlog2n)。 由此推出n个元素的序列采用基于比较的排序方法最坏情况需要O(nlog2n) 次关键字比较，移动次数也是同样的数量级。 基于比较的排序算法的下界为O(nlog2n)，同样可以证明平均时间复杂度 也为O(nlog2n)。 8/69

5. 排序的稳定性 当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排 序的结果不一定唯一。 如果待排序的表中，存在有多个关键字相同的元素，经过排序后这 些具有相同关键字的元素之间的相对次序保持不变，则称这种排序 方法是稳定的。 反之，若具有相同关键字的元素之间的相对次序发生变化，则称这 种排序方法是不稳定的。 9/69

以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。 假设关键字为int类型。待排序的顺序表中元素类型如下： class RecType //顺序表元素类型 { int key; //存放关键字，假设关键字为int类型 String data; //存放其他数据，假设为String类型 public RecType(int d) //构造方法 { key=d; } } 6. 排序数据的组织 10/69