数据结构教学课件ppt作者周颜军王玉茹关伟洲编著第8章排序

第 8 章 排 序 排序是数据结构中的一种基本运算，也是数据处理中经常进行的操作。经统计，排序与查找在计算机的处理时间上占有相当大的比重，可以说排序是执行得最频繁的计算任务之一。它不仅在计算机

第8章 排序 排序是数据结构中的一种基本运算，也是数据处理中经常进行的操作。经统计，排序与查找 在计算机的处理时间上占有相当大的比重，可以说排序是执行得最频繁的计算任务之一。它不仅 在计算机软件系统中占有相当重要的地位，而且与我们的日常生活也密切相关。因此，人们对它 进行了深入细致的研究，设计出大量的排序算法以满足不同的需求，其中包含了不少设计巧妙的 算法。本章只讨论其中的一小部分，但它们却是非常典型、最常用且效率较高的算法。 8.1 基本概念 在讨论排序的问题之前，首先引入排序码的概念。所谓是结点中的一个(或多个)字段， 排序码 该字段的值作为排序运算中的依据。排序码可以是关键字(码)，也可以不是关键字。若排序码为 非关键字，这时可能有多个结点的排序码具有相同的值，因而排序的结果就可能不唯一。排序码 的数据类型可以是整数、实数，也可以是字符串，甚至可以是复杂的组合数据类型。不管排序码 ❶ 是那种数据类型，它应该是满足线性有序关系的量。排序码的字段与类型的选取，应根据实际问 题的要求而定，为了叙述方便而又不失一般性，在以下讨论中，设定排序码均为整型的一个字段。 另外，习惯上，在排序中将结点称为，将一组结点构成的线性表称为。请注意这只是一 记录文件 种习惯性的叫法，不要把它们与外存中的记录、文件混同起来。 sorting ()又称为分类。概要地说，排序就是将待排序文件中的记录按排序码不减(或不增) 排序 的次序排列起来。其确切定义如下： {R, R, …, R}n{K, K, …, K} 设是由个记录组成的文件，是相应的排序码的集合。所 12n12n 1, 2, …, np, p, …, p 谓排序，就是确定的一种排列，使得各排序码满足如下的非递减(或非递 12n 增)关系： KK≤…≤KK≥K≥…≥K ≤（或）。 12 n1 2n pppppp 如果待排序文件中，存在多个排序码相同的记录，经过排序后这些记录仍保持它们原来的相 “” “” 对次序，则称这种排序算法是稳定的。否则称该排序算法是不稳定的。 ❶ 线性有序关系： x, y, z, “<” 对于任意三个数据若关系满足： ①x <yx =yx >y 或者，或者，或者；(三分律) ②x <yy <zx <z 如果，，则。(传递律) “<” 则称关系为线性有序关系。 各种排序方法可以按照不同的原则进行分类。 internal sort 在排序过程中，若整个文件都是放在内存中处理的排序方法称为()；在排 内排序 225