第5章算法与数据结构.ppt

第5章 算法与数据结构 5.1 算法与数据结构的基本概念 5.1.1 算法 算法：是一个有穷的指令集，是解决某一问题 的运算序列。 算法一般应具有以下几个基本特征： （1）可行性。（2）确定性。 （3 ）有穷性。（4）有0个或多个输入。 （5） 有一个或多个输出。 1算法的两个基本要素 （1）对数据对象的运算和操作 1) 算术运算：主要有加、减、乘、除等运算。 2) 逻辑运算：主要有与、或、非等运算。 3) 关系运算：主要有大于、小于、等于、不等 于等运算。 4) 数据传输：主要包括赋值、输入、输出等操 作。 （2）算法的控制结构 算法中各操作之间的执行顺序称为算法的控制 结构。一个算法一般都可以用顺序、选择、循 环三种基本控制结构组合而成。 2算法设计基本方法 （1）列举法 列举法是针对待解决的问题，列举所有可能的 情况，并用问题中给定的条件来检验哪些是必 需的，哪些是不需要的。 （2）归纳法 归纳法是从特殊到一般的抽象过程。通过分析 少量的特殊情况，找出一般的关系。 （3）递归 递归分为直接递归与间接递归两种。如果一个算法A 显式地调用自己则称为直接递归。如果算法A调用另 一个算法B，而算法B又调用算法A，则称为间接递归 调用。 （4）回溯法 通过对待解决的问题进行分析，找出一个解决问题的 线索，然后根据这个线索进行探测，若探测成功便可 得到问题的解，若探测失败，就要逐步回退，改换别 的路经进一步探测，直到问题得到解答或问题最终无 解。 5.1.2 算法的事前估计 我们可以在算法运行之前对算法进行估计。它 可以分为空间复杂度和时间复杂度。 1算法的空间复杂度 算法的空间复杂度是对算法所需存储空间的度 量。 2算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要 的计算工作量。通常，一个算法所用的时间等 于编译时间加上运行时间。 5.1.3 数据结构 数据处理，是指对数据集合中的各元素以各种 方式进行操作，包括插入、删除、查找、更改 等，也包括对数据元素进行分析。 数据的组织方式不同，通常对它进行处理时的 效率也不同。如：对两个存放相同元素的表进 行查找时，一个表中的所有数据元素是没有规 律的，而另外一个表中的元素是经过排序的， 则对于前者用顺序查询法进行查找，后者采用 折半查询法进行查询，可见后者效率较高。 数据结构：是相互之间存在一种或多种特定关 系的数据元素的集合。 数据元素：在数据处理领域中，每一个需要处 理的对象都可以抽象成数据元素。数据元素一 般简称为元素。作为某种处理，其中的数据元 素一般具有某种共同特征。 例如：描述一年四季的季节名“春、夏、秋、冬 ”可以作为季节的数据元素。 表示家庭成员的各成员名“父亲、儿子、女儿” 可以作为家庭成员的数据元素 。 表示数值的各个数“35、21、44、70、66、” 可以作为数值的数据元素。 一般情况下，在具有相同特征的数据元素集合 中，各个数据元素之间存在着关系，这种关系 反映了该集合中的数据元素所固有的一种结构 。在数据处理领域中，通常把数据元素之间这 种固有的关系简单地用前后件关系（或直接前 驱与直接后继关系）来描述。 例如，一年四个季节的顺序关系时，则“春”是“ 夏”的前件（即直接前驱，下同），而“夏”是“ 春”的后件（即直接后继，下同）。 1数据的逻辑结构 所谓数据的逻辑结构，是指描述数据元素之间 逻辑关系的数据结构。数据的逻辑结构由某一 数据对象及该对象中所有数据成员之间的关系 （前后件关系）组成。即一个数据结构可以表 示成： Data_Structure （D，R） 上式中Data_Structure表示数据结构,D是数 据元素的集合, R是D上的关系，它反映了D中 各数据元素之间的前后件关系。 例如： 设a与b是D中的两个数据，则二元组 （a, b）表示a是b的前件，b是a的后件。 例如：一年四季的数据逻辑结构可以表示为： B = (D, R) D =春，夏，秋，冬 R =（春，夏），（夏，秋），（秋， 冬） 2数据的物理结构 数据的物理结构：数据的逻辑结构在计算机中 的存储方式称为数据的物理结构。它包括数据 元素的存储方式和关系的存储方式。 一种数据的逻辑结构根据需要可以表示成多种 存储结构，常用的存储结构有顺序、链接、索 引等存储结构。采用不同的存储结构，其数据 处理的效率是不同的 。 5.1.4 线性结构与非线性结构 空的数据结构：如果在一个数据结构中一个数 据元素都没有，则称该数据结构为空的数据结 构。 在一个空的数据结构中插入一个新的元素后就 变为非空的数据结构。 根据数据元素之间关系的不同特性，一般将数 据结构分为两大类型：线性结构与非线性结构 。 线性结构 ： 如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；（2）每一个结点最 多有一个前件，也最多有一个后件。则称该数 据结构为线性结构。线性结构又称线性表。 如一年四季这个数据结构就属于线性结构，如图 所示。 在一个线性结构中插入或删除任何一个结点后还 应是线性结构。 春夏秋冬 非线性结构: 如果一个数据结构不是线性结构，则称之为非 线性结构。如家庭成员间辈分关系的数据结构 就属于非线性结构，如图所示。 父亲 儿子女儿 显然，在非线性结构中，各数据元素之间的前 后件关系要比线性结构复杂，因此，对非线性 结构的存储与处理比线性结构要复杂得多。 5.2 线性表与线性链表 5.2.1 线性表 1线性表的基本概念 线性表是最简单且最常用的一种数据结构。一 个线性表是n个数据元素的有限序列，表中的 每一个数据元素，除了第一个外，有且只有一 个前件，除了最后一个外，有且只有一个后件 。 线性表或是一个空表，或可以表示为（a1,a2, ,ai, ,an），其中ai (i=1,2, ,n)是属于数据对 象的元素，通常也称其为线性表中的一个结点 。 如26个英文字母的字母表（A, B, C, , Z）是 一个长度为26的线性表，其中的数据元素是单 个字母字符。 在稍微复杂的线性表中，一个数据元素还可以 由若干个数据项组成。例如，某班的学生情况 登记表是一个复杂的线性表，表中每一个学生 的情况就组成了线性表中的每一个元素，每一 个数据元素包括姓名、学号、性别、年龄和健 康状况5个数据项，如表所示。 姓 名学 号性 别年 龄健康状 况 石煜文0204421女20健康 谷红翠0204488女19良好 孟祥欣0204484男21一般 2. 线性表的顺序存储结构 线性表的顺序存储指的是用一组地址连续的存 储单元依次存储线性表的数据元素。线性表的 顺序存储结构具有以下两个基本特点： （1）线性表中所有元素所占的存储空间是连续 的； （2）线性表中各数据元素在存储空间中是按逻 辑顺序依次存放的。 在线性表的顺序存储结构中，如果线性表中各 数据元素所占的存储空间（字节数）相等，则 要在该线性表中查找某一个元素是很方便的。 假设线性表中的第一个数据元素的存储地址为 LOC（b1），每一个数据元素占m个字节，则 线性表中第i个元素bi在计算机存储空间中的存 储地址为： LOC (bi) = LOC (b1) + (i-1)m 在计 算 机 中 的 顺 序 存 储 结 构 如 图 所 示 。 存储地址 LOC (b1) LOC (b1) + m LOC (b1) +(i-1) m LOC (b1) +(n-1) m 占m个字节 占m个字节 占m个字节 占m个字节 b1 b2 bi bn 3. 顺序表的插入操作 在一般情况下，要在第i（1in）个元素之前插 入一个新元素时，首先要从最后一个（即第n 个）元素开始，直到第i个元素之间共n i + 1 元素依次向后移动一个位置，移动结束后，第i 个位置就被空出，然后将新元素插入到第i项。 插入结束后，线性表的长度就增加了1。 图(a)为长度6的线性表顺序存储在长度为7的 存储空间中。现在要求在第5个元素之前插入 一个新元素25。 具体操作步骤为：首先从最后一个元素开始直 到第5个元素，将其中的每一个元素均依次往 后移动一个位置，然后将新元素25插入到第5 个位置。插入一个新元素后，线性表的长度变 成了7，如图（b）所示。这时，为线性表开辟 的存储空间已经满了，如果再要插入，则会造 成称为“上溢”的错误。 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 78 46 25 （a）长度为6的线性表 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 25 78 46 (b）插入元素25后的线性表 4. 顺序表的删除操作 在一般情况下，要删除第i（1in）个元素时， 则要从第i + 1个元素开始，直到第n个元素之间 共n i个元素依次向前移动一个位置。删除结 束后，线性表的长度就减小了1。 图（a）为一个长度为6的线性表顺序存储在长 度为7的存储空间中。现在要求删除线性表中 的第3个元素（即删除元素5）。 具体操作步骤为：从第4个元素开始直到最后 一个元素，将其中的每一个元素均依次往前移 动一个位置。此时，线性表的长度变成了5， 如图（b）所示。 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 78 46 （a）长度为6的线性表 1 2 3 4 5 6 7 V (1:7) 15 33 21 78 46 （b）删除元素5后的线性表 5.2.2 线性链表 线性表的顺序存储结构具有简单、操作方便等 优点。但在做插入或删除操作时，需要移动大 量的元素。因此，对于大的线性表，特别是元 素变动频繁的大线性表不宜采用顺序存储结构 ，而是通常采用链式存储结构。 在链式存储结构中，存储数据结构的存储空间 可以不连续，各数据结点的存储顺序与数据元 素之间的逻辑关系可以不一致。链式存储方式 既可用于表示线性结构，也可用于表示非线性 结构。 假设数据结构中的每一个数据结点对应于一个 存储单元，这种存储单元称为存储结点，简称 结点。在链式存储方式中，要求每个结点由两 部分组成：一部分用于存放数据元素值，称为 数据域；另一部分用于存放指针，称为指针域 。其中指针用于指向该结点的前一个或后一个 结点，从而可以表示数据元素之间的逻辑关系 。 我们把线性表的链式存储结构称为线性链表 。线性链表中存储结点的结构如图所示: 存储地址 i 数据域指针域 V (i)NEXT (i) 在线性链表中，用一个专门的指针H（称为头 指针）指向线性链表中第一个数据元素的结点 （即存放线性表中第一个数据元素的存储结点 的序号）。从头指针开始，沿着线性链表各结 点的指针可以扫描到链表中的所有结点。线性 表中最后一个元素没有后件，因此，线性链表 中最后一个节点的指针域为空（用、NULL或 0表示），表示链表终止。当头指针H = NULL （或0）时称为空表。 在某些应用中，对线性链表中的每个结点设置 两个指针，一个称为左指针，用以指向其直接 前驱；另一个称为右指针，用以指向其直接后 继。这样的线性链表称为双向链表。 5.2.3 对线性链表的基本操作 1. 在线性链表中查找指定的元素 在非空线性链表中寻找包含指定元素值x的前 一个结点n的操作过程为： 从头指针指向的结点开始向后沿指针进行扫描 ，直到后面已经没有结点或下一个结点的数据 域为x为止。 因此，由这种方法找到的结点n有两种可能： 当线性链表中存在包含元素x的结点时，则找 到的n为首次发现的包含元素x的前一个结点序 号；当线性链表中不存在包含元素x的结点时 ，则找到的n为线性链表中的最后一个结点序 号。 2. 线性链表的插入 线性链表的插入操作是指在线性链表中的指定 位置上插入一个新的元素。为了要在线性链表 中插入一个新元素，首先要为该元素申请一个 新结点，以存储该元素的值。然后将存放新元 素值的结点链接到线性链表中指定的位置。 3. 线性链表的删除 线性链表的删除是指在线性链表中删除包含指 定元素的结点。 为了在线性链表中删除包含指定元素的结点， 首先要在线性链表中找到这个结点，然后将要 删除结点释放，以便于以后再次利用。 4. 循环链表及其基本操作 循环链表的结构与前面所讨论的线性链表相比 ，具有以下两个特点： （1）在循环链表中增加了一个表头结点，表头 结点的数据域可以是任意值，也可以根据需要 来设置，指针域指向线性表的第一个元素的结 点。循环链表的头指针指向表头结点。 （2）循环链表中最后一个结点的指针域不为空 ，而是指向表头结点。从而在循环链表中，所 有结点的指针构成了一个环。 5.3 栈和队列 5.3.1 栈 1. 什么是栈 栈实际上是一种特殊的线性表。在这种特殊的 线性表中，插入与删除操作都只在线性表的一 端进行。因此，栈是指被限定仅在一端进行插 入与删除操作的线性表。 在栈中，允许插入与删除的一端称为栈顶，而 不允许插入和删除的另一端称为栈底。栈是按 照“后进先出”的原则组织数据的，因此，栈也 被称为“后进先出”的线性表。在程序设计语言 中，一般用一维数组作为队列的顺序存储空间 。 通常用指针top来指示栈顶的位置，用指针 bottom指向栈底。向栈中插入一个元素称为进 栈操作，从栈中删除一个元素称为出栈操作。 栈顶指针top动态反映了栈中元素的变化情况 。图是栈的示意图。 栈顶 top 栈底 bottom 进栈 出栈 bn b2 b1 2. 对栈的操作 对栈的基本操作有两种：进栈和出栈。 （1）进栈操作 进栈操作是指在栈顶位置插入一个新元素。其 过程是：先将栈顶指针加一，然后将新元素放 到栈顶指针指向的位置。当栈顶指针已经指向 存储空间的最后一个位置时，说明栈空间已满 ，不能再进栈，这种情况称为栈“上溢”错误。 （2）出栈操作 出栈操作是指取出栈顶元素。其过程是：先将 栈顶指针指向的元素赋给一个指定的变量，然 后将栈顶指针减1。当栈顶指针为0时，说明栈 空，不能再出栈，这种情况称为栈“下溢”错误 。 5.3.2 队列 1. 什么是队列 队列是指只允许在一端进行插入、而在另一端 进行删除的线性表。允许插入的一端称为队尾 ，通常用一个称为尾指针（rear）的指针指向 队尾元素；允许删除的一端称为队头，通常也 用一个队头指针（front）指向队头元素的前 一个位置。队列是按照“先进先出”的原则组织 数据的，因此队列又称为“后进后出”的线性表 。 在队列中，队尾指针rear与队头指针front共 同反映了队列元素中元素动态变化的情况。下 图是队列的示意图。 出队abcde进队 front rear 向队列的队尾插入一个元素称为进队操作，从 队列的队头删除一个元素称为出队操作。 由上图可知：在队列的末尾插入一个元素（进 队操作）只涉及队尾指针rear的变化，而要删 除队列中的队头元素（出队操作）只涉及队头 指针front的变化。 2. 循环队列及其操作 循环队列是一种将顺序队列臆造为一个环状的 空间的方法，通过把存储队列元素的表在逻辑 上看成一个环，将队列存储空间的第一个位置 作为队列最后一个位置的下一个位置，供队列 循环使用。 循环队列的初始状态为空，即rear = front = m，如图所示。 A (1: n) n 2 1 A.rear A.front 在循环队列中，用队尾指针rear指向队列中的 队尾元素，用队头指针front指向队头元素的 前一个位置，因此，从队头指针front指向的 后一个位置直到队尾指针rear指向的位置之间 所有的元素均为队列中的元素。 循环队列主要有两种基本操作：进队操作与出 队操作。每进行一次进队操作，队尾指针加一 。当队尾指针rear = n + 1时，则置rear = 1。 每进行一次出队操作，队头指针就加一。当队 头指针front = n + 1时，则置front = 1。 为了能区分队列满还是队列空，通常还需增加 一个标志s，s值的定义如下： 由此可以得出队列空与队列满的条件如下： 队列空的条件为s = 0；队列满的条件为s = 1且 front = rear。 5.4 树与二叉树 5.4.1 树的基本概念 树是一种重要的非线性结构。在这种数据结构 中，所有数据元素之间的关系具有明显的层次 特性，并以分支关系定义了层次结构。下图是 一棵树的例子。 A EDCB IHGF QN J RKM 现实世界中有很多可以用树来表示的例子。例 如图中的树表示了高校中院系之间的关系。 沈阳工业大学 信息学院外语学院理学院经济学院 软件 教研室 控制 教研室 英语 教研室 德语 教研室 数学 教研室 物理 教研室 宏观经 济 教研室 微观经 济教研 室 树中每一个结点只有一个直接前驱，称作父结 点。没有直接前驱的结点只有一个，称作树的 根结点，简称为树的根。例如，在上图中，结 点沈阳工业大学是树的根结点。每一个结点可 以有多个直接后继，它们都称为该结点的子女 。没有直接后继的结点称为叶子结点（如：图 中的结点理学院、数学教研室等）。 除树根以外的其它结点被划分为多个互不相交 的有限集合，每个集合又是一棵树，被称为根 的子树。结点所拥有的子树的棵树被称为该结 点的度。 如上图中沈阳工业大学根节点 的度是4，理学 院的度是2，树中所有结点的度的最大值称为 树的度。例如，图中所示的树的度为4。 用树来表示算术表达式的原则如下： （1）算术表达式中的每一个运算符对应于树中 的一个结点。 （2）运算符的任一运算对象皆为该运算符结点 的子树。 （3）运算对象中的单个变量均为叶子结点。 下图是用树结构对表达式a + b/(c-d) - (x, y, z)*e 的表示。注意：表示一个表达式的表达式 树可能并不唯一。 - + /a -b dc * e a+b/(c- d) b/(c-d) c- d (x, y, z) (x, y, z)*e xyz 5.4.2 二叉树及其基本性质 1. 什么是二叉树 二叉树是另一种树型结构，当然二叉树也是一 种非线性结构。它的特点是： （1）非空二叉树只有一个根结点； （2）每一个结点最多有两棵子树，顺序不能颠 倒，分别称为该结点的左子树与右子树。 可见在二叉树中，不存在度大于2的结点，从 而所有子树也均为二叉树。另外，在二叉树中 ，一个结点可以只有左子树而没有右子树，也 可以只有右子树而没有左子树。当一个结点既 没有左子树也没有右子树时，该结点即是叶子 结点。 下图是一棵深度为3的二叉树。 A C E B F 2. 二叉树的基本性质 性质1 在二叉树的第i层上，最多有 （i1） 个结点。 性质2 深度为m的二叉树最多有 -1个结点。 性质3 在任意一棵二叉树中，度为0的结点（即 叶子结点）总是比度为2的结点多一个。 性质4 具有n个结点的二叉树，其深度至少为 log2n+1，其中log2n表示取log2n的整数部分 。 2i-1 2m 3. 满二叉树与完全二叉树 满二叉树与完全二叉树是两种特殊形态的二叉 树。 （1）满二叉树 满二叉树是一棵深度为m且有 -1个结点的二 叉树。该二叉树每一层上的所有结点数都达到 最大值。 2m (a) 深度为2的满二 叉树 (b) 深度为3的满二 叉树 A B CDE F G A BC （2）完全二叉树 完全二叉树除最后一层外，每一层上的结点数 均达到最大值；在最后一层上只缺少右边的若 干结点 ，称之为完全二叉树 。 A C DFE B 由满二叉树与完全二叉树的特点可以看出，满 二叉树也是完全二叉树，而完全二叉树一般不 是满二叉树。 5.4.3 二叉树的存储结构 在计算机中，二叉树通常采用链式存储结构。 用于存储二叉树中各元素的存储结点由两部分 组成：数据域与指针域。但在二叉树中，由于 每一个元素可以有两个子结点，因此，用于存 储二叉树的存储结点的指针域有两个：一个用 于指向该结点的左子结点，称左指针域；另一 个用于指向该结点的右子结点，称为右指针域 。 由于二叉树的存储结构中每一个存储结点有两 个指针域，因此，二叉树的链式存储结构也称 为二叉树链表。 5.4.4 二叉树的遍历 二叉树的遍历： 是指不重复地访问二叉树中的所有结点。 在遍历二叉树的过程中，一般先遍历左子树， 然后再遍历右子树。在先左后右的原则下，根 据访问根结点的次序，二叉树的遍历可以分为 三种：前序遍历、中序遍历、后序遍历。 1. 前序遍历 所谓前序遍历是指首先访问根结点，然后遍历 左子树，最后遍历右子树；并且，在遍历左、 右子树时，仍然先访问根结点，然后遍历左子 树，最后遍历右子树。 下面是二叉树中序遍历的简单描述： 若二叉树为空，则结束返回。否则： （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 2. 中序遍历 所谓中序遍历是指首先遍历左子树，然后访问 根结点，最后遍历右子树；并且，在遍历左、 右子树时，仍然先遍历左子树，然后访问根结 点，最后遍历右子树。 下面是二叉树中序遍历的简单描述： 若二叉树为空，则结束返回。否则： （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 3. 后序遍历 所谓后序遍历是指首先遍历左子树，然后遍历 右子树，最后访问根结点，并且，在遍历左、 右子树时，仍然先遍历左子树，然后遍历右子 树，最后访问根结点。 下面是二叉树后序遍历的简单描述： 若二叉树为空，则结束返回。否则： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 5.5 查找和排序技术 5.5.1 查找技术 1. 顺序查找 顺序查找的基本方法是：从线性表的第一个元 素开始，逐个将线性表中的元素与被查元素进 行比较，若相等则表示找到（即查找成功）； 若线性表中所有的元素都与被查元素进行了比 较但都不相等，则表示线性表中没有要找的元 素（即查找失败）。 虽然顺序查找的效率不高，但在下列两种情况 下只能采用顺序查找： （1）如果线性表为无序表，则只能用顺序查找 。 （2）采用链式存储结构的有序线性表，只能采 用顺序查找。 2. 折半查找 折半查找只适用于顺序存储的有序表，也就是 说，线性表中的元素已经按值非递减排列。 假设有序线性表的长度为m，被查元素值为x， 则折半查找的方法如下： 将x与线性表的中间项的元素值进行比较，若 中间项的值等于x，则查找成功，结束返回； 若x小于中间项的值，则在线性表的前半部分 用相同的方法进行查找；若x大于中间项的值 ，则在线性表的后半部分用相同的方法进行查 找。这个过程一直进行到查找成功或线性表中 没有这个元素为止。 5.5.2 排序技术 1. 插入排序 所谓插入排序，是指将无序序列中的各元素依 次插入到已经有序的线性表中。 （1）简单插入排序 简单插入排序的基本思想是：将一个新元素插 入到已经排好序的有序序列中，从而元素的个 数增一，并成为新的有序序列。 在简单插入排序过程中，由于每一次比较后最 多去掉一个逆序，因此，这种排序方法的效率 在最坏情况下，需要n(n-1)/2次比较。 （2）希尔排序 希尔排序的基本思想是：将整个初始序列分割 成若干个子序列，对每个子序列分别进行简单 插入排序，最后再对全体元素进行一次简单插 入排序。由此可见，希尔排序也是一种插入排 序方法。 2交换排序 所谓交换排序是指借助数据元素之间的互相交 换进行排序的一种方法。冒泡排序法与快速排 序法都属于交换类的排序方法。 （1）冒泡排序 冒泡排序的过程简单，它的基本思想是通过对 相邻元素进行比较，并根据比较的结果交换位 置，从而逐步由任意序列变为有序序列。 具体过程是：首先，将第一个元素和第二元素进行比 较，若为逆序，则交换之。接下来对第二个元素和第 三个元素进行同样的操作，并依次类推，直到倒数第 二个元素和最后一个元素为止。其结果是将最大的元 素交换到了整个序列的尾部。这个过程叫做第一趟冒 泡排序。而第二趟冒泡排序是在除去这个最大元素的 子序列中从第一个元素起重复上述过程，直到整个序 列变为有序为止。排序过程中，小元素好比水中气泡 逐渐上浮，而大元素好比大石头逐渐下沉，冒泡排序 故此得名。 假设初始序列的长度为n，冒泡排序需要经过n-1 趟排序，需要的比较次数为n(n-1)/2。下图是 冒泡排序的示意图。 初始序列 第一趟排序后 第二趟排序后 第三趟排序后 第四趟排序后 第五趟排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54 （2）快速排序 快速排序法就是一种可以通过一次交换而消除多个逆序 的排序方法。其基本思想如下： 任取待排序序列中的某个元素对象作为基准，按照该 元素值的大小，将整个序列划分为左右两个子序列（ 这个过程称为分割）：左侧子序列中所有元素的值都 小于或等于基准对象元素的值，右侧子序列中所有元 素的值都大于基准对象元素的值，基准对象元素则排 在这两个子序列中间（这也是该对象最终应该被安放 的位置），接下来分别对这两个子序列重复进行上述 过程，直到所有的对象都排在相应位置上为止。 3选择排序 选择排序的基本思想是：每一趟排序过程都是 在当前位置后面剩下的待排序对象中选出元素 值最小的对象，放到当前的位置上。 （1）简单选择排序 简单选择排序的基本步骤是： 1) 在一组对象SiSn-1中选择元素值最小的对 象； 2) 若它不是这组对象中的第一个对象，则将它与 这组对象中的第一个对象对调； 3) 在剩下的对象中重复执行上述两步，直到只剩 下一个对象为止。 下图是这种排序法的示意图，图中有方框的元素是刚 被选出来的最小元素。 原序列943561537791239 第1遍选择935615377941239 第2遍选择92615377943539 第3遍选择912355377946139 第4遍选择912353977946153 第5遍选择912353953946177 第6遍选择912353953619477 第7遍选择912353953617794 （2）堆排序 堆排序法属于选择类的排序方法。堆的定义如下： 具有n个元素的序列（a1，a2,，an），当且仅当满足 （i = 1，2，n/2）时称之为堆。 根据堆的定义和堆的调整过程，可以得到堆排 序的方法如下： （1）首先将一个无序序列建成堆。 （2）然后将堆顶元素与堆中最后一个元素交换 ，并将除了已经换到最后的那个元素之外的其 它元素重新调整为堆。 反复做第（2）步，直到所有的元素都完成交 换为止，从而得到一个有序序列。 堆排序的方法对于规模较小的线性表并不合适 ，但对于较大规模的线性表来说是很有效的。