第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
排序算法的性能由算法的时间和空间确定的，而时间又是由比较和移动的次数确定的。若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素为正序。反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表中元素为反序。6/69
排序算法的性能由算法的时间和空间确定的，而时间又是由比较 和移动的次数确定的。 若待排序元素的关键字顺序正好和排序顺序相同，称此表中元素 为正序。 反之，若待排序元素的关键字顺序正好和排序顺序相反，称此表 中元素为反序。 6/69
基于比较的排序算法的下界n=3的决策树(R1,R2,R3)k1≤k2(R1,R2,Rg)(R2,R1,R3)k,≤k3ki≤k3是是否否V①④(R1,R3,R2)(R2,R3,R1)k≤k3k,≤k3(Ri,R2,Rg)(R2,R1,R,)是是否否③5?(R1,R3,R2)(R3,R1,R2)(R2,R3,R1)(R3,R2,R1)正序不变，逆序交换！3！=6个叶子结点7/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=1og2(2n!)=1og2n!+1，而1og2n!=nlog2n，即h=o(nlog2n)。由此推出n个元素的序列采用基于比较的排序方法最坏情况需要o(nlog2n)次关键字比较，移动次数也是同样的数量级。基于比较的排序算法的下界为o(nlog,n)，同样可以证明平均时间复杂度也为o(nlog2n)。8/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
5. 排序的稳定性 当待排序元素的关键字均不相同时，排序的结果是唯一的，否则排 序的结果不一定唯一。 如果待排序的表中，存在有多个关键字相同的元素，经过排序后这 些具有相同关键字的元素之间的相对次序保持不变，则称这种排序 方法是稳定的。 反之，若具有相同关键字的元素之间的相对次序发生变化，则称这 种排序方法是不稳定的。 9/69
6.排序数据的组织以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。假设关键字为int类型。待排序的顺序表中元素类型如下：//顺序表元素类型class RecType//存放关键字，假设关键字为int类型( int key;1/存放其他数据，假设为String类型String data;1/构造方法publicRecType(int d){ key=d;}10/69
以顺序表作为排序数据的存储结构（除基数排序采用单链表外）。 假设关键字为int类型。待排序的顺序表中元素类型如下： class RecType //顺序表元素类型 { int key; //存放关键字，假设关键字为int类型 String data; //存放其他数据，假设为String类型 public RecType(int d) //构造方法 { key=d; } } 6. 排序数据的组织 10/69