第三章 算法与数据结构

1、第三章 算法与数据结构设计程序首先要了解需要研究要解决的问题，提出适当的计算模型并列出解决问题的方法和步骤,模型一旦建立起来，就要选择合适的算法，并将解题步骤表述出来本章着重讨论解决问题的核心 - 以及算法的处理对象 - 31算法解题过程的准确、完整的描述称作解该问题的就是用计算机语言表述的算法，就是图形化了的算法程序算法数据结构算法由操作与控制结构两要素组成(1) 1) 逻辑运算：逻辑运算： “ “与与”、“或或”、“非非”；(2) (2) 算术运算：算术运算： 加、减、乘、除；加、减、乘、除；(3) (3) 数据比较：数据比较： 大于、小于、等于、不等于；大于、小于、等于、不等于；(4)

2、(4) 数据传送：数据传送： 输入、输出、赋值。输入、输出、赋值。2. 控制结构算法的控制结构，决定了各操作的执行次序。用可以形象地表示出算法的控制结构任何复杂的算法都可以用顺序、选择、循环三种控制结构组合而成S1S2BS1S2BS(a)(b)(c)S3FTBFT(d)S3.1.2 3.1.2 算法的特征算法的特征1. 算法是由一套计算规则组成的一个过程2. 组成算法的规则是确定的、可执行的3. 每种算法必须有确定的结果，产生一个或多个输出4. 每个算法必须有0个（自动生成初始数）或多个输入5. 解答必须在有限步内得到,不能出现“死循环”：算法是一个过程，这个过程由一套明确的规则组成，这些规则

3、指定了一个操作的顺序，以便用有限的步骤提供特定类型问题的解答3.1.3 3.1.3 算法的表示算法的表示 算法设计一般是由粗到细的过程，一般可以使用下面几种类型的工具描述算法:自然语言描述算法通俗易懂，但它有着难以克服的缺陷：(1) 易产生歧义性 (2) 语句繁琐冗长，很难清楚地表达算法的逻辑流程(3) 当今的计算机尚不能处理用自然语言表示的算法常用的有流程图、PAD图和N-S图、伪代码等为了便于转换成某种编程语言，一般采用准程序设计语言作算法描述语言。这里为类VB语言继续 流程图 是采用不同的几何图形来描述算法的逻辑结是采用不同的几何图形来描述算法的逻辑结构，每个几何图形表示不同性质的操作构

4、，每个几何图形表示不同性质的操作开始结束(a) 起止框、连接框(b) 输入输出框AA输入a,bN10(c) 判断框truefalse(d) 处理框i+1i(e) 注释框(f) 流向线N为正整数返回1.1.枚举法（枚举法（穷举法基本思想是：先依据题目的部分条件确定答案的大致范围在此范围内对所有可能的情况逐一验证，直到全部情况验证完若某个情况使验证符合题目的条件，则为本题的一个答案；若全部情况验证完后均不符合题目的条件，则问题无解2.迭代法使一个复杂问题的求解过程转化为相对简单的迭代算式的重复执行过程使用迭代法构造算法的基本方法是：首先确定一个合适的迭代公式，选取一个初始近似值以及解的误差然后用循

5、环处理实现迭代过程，终止循环过程的条件是前后两次得到的近似值之差的绝对值小于或等于预先给定的误差并认为最后一次迭代得到的近似值为问题的解。3.递归法如果一个过程直接或间接地调用它自身，则称该过程是递归的例：求阶乘。Func fac(n As Integer) If n=1 then fac=1 Else fac=n*fac(n-1) Endif 1 n=0n! n(n-1)! n0递归过程必须有一个递归终止条件，当n=0时定义为1，是阶乘递归定义的递归出口递归则是从函数本身出发，逐次上溯调用其本身求解过程，直到递归的出口，然后再从里向外倒推回来，得到最终的值4.递推法所谓递推法，它的数学公式也

6、是递归的。只是在实现计算时与递归相反。从给定边界出发逐步迭代到达指定计算参数。例：求阶乘f(n)n! n(n-1)! nf(n-1)要计算10!，可以从递推初始条件f(0)=1出发，应用递推公式f(n)=nf(n-1)逐步求出f(1)、f(2)、f(9)、最后求出f(10)的值递推操作是提高递归函数执行效率最有效的方法，科技计算中最常见5.分治法解一个夏杂的问题时，尽可能地把这个问题分解为较小部分，找出各个的解，然后再把各部分的解组合成整个问题的解，这就是所谓的分治法在那些涉及到寻找一组解的问题或者满足某些约束条件的最优解的问题中，有许多可以用回溯法来求解回溯法的算法是：确定起始状态值走第一步

7、 确定下一步还有几种可能 选一可能走下一步，记住可能和本步特征做完新一步应做的事 While While 目标未达到目标未达到 dodo 确定下一步有几种可能 While While 没有可能没有可能and and 还有上一步还有上一步 dodo 回退上一步 查有无下一可能 EnddoEnddo If If 上一步没有了上一步没有了ThenThen return (SUCC=FALSE) EndIfEndIf选一可能走一步，记住可能和本步特征 做完新一步应做的事EnddoEnddoreturn (SUCC=TRUE)return (SUCC=TRUE)3.2 数据结构 3.2.1 数据结构概述

8、 。 数据的逻辑结构、数据的存储结构、数据的运算：Data-Structure (D,R)其中：D是数据元素的集合，R是D上关系的集合 一般将数据结构分为两大类：线性数据结构和非线性数据结构和非线性数据结构线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图 程序中的数据运算数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等2 2数据结构应用示例数据结构应用示例例例3.43.4识别“体”字的过程丿乙亻刂借何体 休体休判断偏旁部首四角号码匹配局部匹配按分支和层次组织的数据

9、，称为：例例3.5计算机换房系统中的“多角互换问题”甲甲乙乙丙丁数据结构叫它们为例例3.6 3.6 饭店服务系统中的客房预订问题刘佳4.14双间张大明5.1单间王仁3.24双间黄超8.12三间头尾这种结构称为“，是一种元素间先后次序很强的数据结构例例3.7 管理信息系统中的查询问题各种计算机管理信息系统中，通常相关的信息(记录)组成一个文件,文件文件是一类很重要的数据结构文件中的记录可按顺序方式组织黄鹏8211编译原理刘东8201算法分析李季为8211编译原理李宾8202算法分析王华8202图形学杜可翔8201编译原理何平8201编译原理陈红英8211算法分析姓名班级选修课链链头(b)(a)黄

10、鹏8211编译原理刘东8201算法分析李季为8211编译原理李宾8202算法分析王华8202图形学杜可翔8201编译原理何平8201编译原理陈红英8211算法分析姓名班级选修课链链头(b)(a)顺序文件导出的链表为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为3.2.2 线性表线性表的逻辑结构是n个数据元素的有限序列:(a1, a2 ,a3,an) n为线性表的长度(n0)，n=0的表称为空表数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素； 除最后一个元素外，每个元素都

11、有且只有一个后继元素。所有数据元素ai在同一个线性表中必须是相同的数据类型线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为；用链式存储结构存储的线性表称为线性表的基本运算主要有：(1)在两个确定的元素之间插入一个新的元素；(2)删除线性表中某个元素；(3)按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为就是用顺序方式存储的线性表，其下标可看成元素的相对地址运算：，在线性表(a1, a2，ai，ai+1，an)的第i个位置插入元素x，算法如下：PROC INSERT (VAR A,VAR n,i,x

12、)If(in+1) Then ERROR(“位置不存在！”) Else For j=n Down To i A(j+1)=A(j) Next j Endif A(i)=x n=n+1 End：在表长为n的线性表(a1,a2,ai-1,ai+1an)中删除第i个数据元素，通常还需将第i+1个至第n个元素向前推动一个位置，即(a1, a2 ,，ai-1,ai+1，an)，其算法描述如下:PROC DELETE (VAR A,VAR n,I)PROC DELETE (VAR A,VAR n,I)If (in) Then ERROR (位置不存在！) ELSE FOR j=i TO n-1 A(j)=

13、A(j+1) Next j n=n-1 EndifEndEnd在顺序表中插入或删除在顺序表中插入或删除元素时，每进行一次插元素时，每进行一次插入或删除，都要移动近入或删除，都要移动近乎一半的元素乎一半的元素。对于长度可变的线性表，对于长度可变的线性表，必须按可能达到的最大必须按可能达到的最大长度分配空间长度分配空间：2链表( (线性链表线性链表):):链式存储的线性表链式存储的线性表结点除信息域外还含有一个指针域，用来指出其后结点除信息域外还含有一个指针域，用来指出其后继结点的位置继结点的位置最后一个结点没有后继结点，指针最后一个结点没有后继结点，指针它的指针域为空它的指针域为空( (记为记为

14、NIL NIL 或或)。另外还需要设置一个指针。另外还需要设置一个指针headhead，指向单链表的第一个结点指向单链表的第一个结点infonext信息域指针域 链表的一个重要特点是插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可abHeadabHeadx acHeadb (2）循环链表：循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为“NIL”，而是指向头一个结点，成为一个由链指针链结的环设有一个指向后继结点的指针和一个指向前驱结点的指针结点1结点2结点n3栈栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定

15、性数据结构栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)栈的物理存储可以用顺序存储结构，也可以用链式存储结构( (设置一个空栈设置一个空栈判定栈是否为空判定栈是否为空进栈、退栈进栈、退栈读取栈顶元素等读取栈顶元素等1 进栈 PROCEDURE PUSHSTACK (VAR STACK，m，VAR top，x) 注释：在栈 STACK(1:m)的栈顶 top 之上插入元素 x BEGIN IF top=m THEN ERROR (“栈满！”) ELSE top=top+1 注释：栈顶上移 STACK(top)=x 注释：将 x 放入栈顶 ENDI

16、F END2 退栈 FUNCTION POPSTACK (VAR STACK，VAR top，VAR y)：VAR注释：当栈空时返回函数值 FALSE，反之退出栈顶元素赋给变量 y 并返回函数值 TRUE BEGIN IF top=0 THEN RETURN (FALSE) ELSE y=STACK(top) 注释：将栈顶元素赋给变量 y top=top-1 注释：栈顶下移 RETURN (TRUE) ENDIF END 4队列(1）队列的结构特点队列队列( (Queue)Queue)是限定所有的插入只能在表的一端是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线进行，而所

17、有的删除都在表的另一端进行的线性表性表表中允许插入的一端称为队尾表中允许插入的一端称为队尾( (Rear)Rear)，允许删除允许删除的一端称为队头的一端称为队头( (Front)Front)队列的操作是按先进先出的原则进行的队列的操作是按先进先出的原则进行的队列的物理存储可以用顺序存储结构，也可以用队列的物理存储可以用顺序存储结构，也可以用链式存储结构。链式存储结构。a1 a2 a3 an入队列出队列头尾(2）队列的运算：设置一个空队列；判定队列是设置一个空队列；判定队列是否是空队列；入队列；出队列；读取队头元素等否是空队列；入队列；出队列；读取队头元素等如果队列的容如果队列的容量无法预先量

18、无法预先估计时，可估计时，可以采用链表以采用链表存储结构存储结构AABBBCBCDCDECD初态插入A插入B删除A插入C插入D删除B插入EFRFRFRFRFRRFRFFR循环队列的插入、删除循环队列的插入、删除队尾队头FrontRear3.2.3 串串串( (String)String)可以看作一维字符数组，但其长度不恒定，可以看作一维字符数组，但其长度不恒定，可以作删除、插入操作可以作删除、插入操作许多高级语言把串作为一种单独的类型，其元素不可许多高级语言把串作为一种单独的类型，其元素不可作四则运算作四则运算进行连接、删除、插入操作，用子串有时很方便进行连接、删除、插入操作，用子串有时很方便

19、子串子串( (Substring)Substring)是串的一部分，具有串的一切特征是串的一部分，具有串的一切特征3.2.4 树和二叉树1.树和二叉树的定义和术语： 树(Tree)是由 一个或多个结点 组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m0)个互不相交的有限集T1,T2,T3 ,Tm，每一个集合本身又是一棵树，且称为根的子树：(A(B(E,F),C(G),D(H,I,J)结点子树个数为结点的度,结点度的最大值为该树的度结点B的度为2，树的度为3AAFEDCBJHIG0棵或多棵不相交的树的集合称为是另一种重要的树形结构，其结构定义为：二叉树(Binary Tree

20、)是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树AGDCBIHEF2.树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理Edatapoint1point2point3ABCDFGHIJroot(a)(b)3.3.二叉树的存储结构二叉树的存储结构LCDATARCroot(a)(b)ABCDEGFHIABCD

21、DATAEFGHI2400LC780003560RC090001root123456789123456789(c)可使用具有可使用具有2 2个指针域的链表，个指针域的链表，LCLC为左指针域，指向为左指针域，指向结点的左子树，结点的左子树，RCRC为右指针域，指向结点的右子树。为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数亦可用数组的下标来模拟指针，即开辟三个一维数组组DATADATA，LCLC和和RCRC分别存放结点的元素及其左、右指分别存放结点的元素及其左、右指针针4.树的二叉树表示每一棵都能唯一地转换到它所对应的二叉树每一棵都能唯一地转换到它所对应的二叉树转换

22、方法：凡是兄弟就用线连接起来，对每个非终转换方法：凡是兄弟就用线连接起来，对每个非终端结点，除其最左孩子外，删去该结点与其他孩端结点，除其最左孩子外，删去该结点与其他孩子结点的连线，再以根结点为轴心，顺时针旋转子结点的连线，再以根结点为轴心，顺时针旋转45450 0AGDCBIHEFJAAFEDCBJHIG5.树和二叉树的遍历(周游)树的遍历根据树的递归定义，有两种遍历树的方法：(1)先根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先访问树的根结点，然后依次先根遍历每棵子树。(2)后根(次序)遍历：若树中只有一个根结点，则访问树的根结点； 否则，首先依次后根遍历每一棵子树，

23、然后访问树的根结点。二叉树的遍历(3)后序遍历二叉树的算法为： 若二叉树不空，则： a) 后序遍历左子树； b) 后序遍历右子树； c) 访问根结点。前图用后序遍历为：FEGJIHDCBA( 若二叉树不空，则：若二叉树不空，则： a) a) 访问根结点；访问根结点； b) b) 前序遍历左子树；前序遍历左子树； c) c) 前序遍历右子树。前序遍历右子树。前图用前序遍历为前图用前序遍历为ABEFCGDHIJABEFCGDHIJ(2)(2)中序遍历二叉树的算法为：中序遍历二叉树的算法为： 若二叉树不空，则作：若二叉树不空，则作： a) a) 中序遍历左子树；中序遍历左子树； b) b) 访问根结

24、点；访问根结点； c) c) 中序遍历右子树。中序遍历右子树。前图用中序遍历为：前图用中序遍历为：EFBGCHIJDAEFBGCHIJDA3.2.5 图1.图的概念和术语常用G=(V,E)代表一个图，V是结点的有穷集合(非空)，E是边的有穷集合(E可为空集)。若一条边的结点对无序，则称无向图。(V1,V2)和(V2,V1)相同有向图由顶点的非空有限集和边的有限集组成。(V1,V2)和(V2,V1)表示不同边n个顶点的无向图边的最大数目是n(n-1)/2。n个顶点的有向图边的最大数目为n2（双环且自环）。若(V1, V2)E，则称V1和V2是。边(V1, V2)是V1和V2相关联的边。一个是与该

25、结点相关联的边的数目。对于有向图，则把以结点Vi为终点的边的数目称结点Vi的； 把以Vi为始点的边的数目称为Vi的。出度为0的结点称为终端结点。V1V2V3V42.图的存储(1)图的相邻矩阵表示法Ai,j =1，若(Vi，Vj)是图 G 的边0，若(Vi，Vj)不是图 G 的边例如：例如：若若G是一个具有是一个具有n个结点的图，则个结点的图，则G的相邻矩阵是的相邻矩阵是: 有向图及其相邻矩阵返回返回38无向图及其相邻矩阵带权图及其相邻矩阵返回返回39(2)图的邻接表表示法例例1：右图有7个顶点最大的度是4，则选用75矩阵，将每个顶点可达顶点列入如下图返回返回40V1V2V3V4V1V2V3V4

26、12342111332244结点表边表用邻接表法表示有向图，根据需要可以保存每个用邻接表法表示有向图，根据需要可以保存每个结点的出边表，也可以保存每个结点的入边表结点的出边表，也可以保存每个结点的入边表例例2（3）边目录3.图的遍历(1)深度优先遍历基本思想是：从图中某个V出发，访问此结点，再依次访问所有与V有路径的结点。完成后再另选图中一个未被访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止。(2)广度优先遍历基本思想是：从某个结点V出发，访问此结点，再依次访问V邻接的未访问结点。再从这些结点出发进行广度优先遍历，直至图中所有被访问过的结点的相邻结点都被访问到。完成后另选图中一

27、个未曾访问的结点作始点，重复上述过程，直至图中所有结点都被访问到为止3.3 3.3 查找查找3.3.1 3.3.1 基本概念基本概念是数据元素中可以唯一标识一个数据元素的是数据元素中可以唯一标识一个数据元素的数据项，比如学号、身份证号等，数据项，比如学号、身份证号等，是根据给定的关键值，在一组数据中确定一个是根据给定的关键值，在一组数据中确定一个其关键字等于给定值的数据元素的过程其关键字等于给定值的数据元素的过程：给定一个值：给定一个值K K，在含有在含有n n个记录的文件中进个记录的文件中进行搜索，寻找一个其关键字等于给定的行搜索，寻找一个其关键字等于给定的K K值的记录，值的记录，如找到，

28、则输出记录或记录在文件中的相对位置称如找到，则输出记录或记录在文件中的相对位置称查找成功；否则输出查找不成功的信息称查找失败。查找成功；否则输出查找不成功的信息称查找失败。 3.3.2 3.3.2 查找算法查找算法1.1.顺序查找顺序查找顺序查找的方法是：用待查关键字值与线性表中各结点的顺序查找的方法是：用待查关键字值与线性表中各结点的关键字值逐个比较，直到找出相等的关键字值关键字值逐个比较，直到找出相等的关键字值; ;或找遍所或找遍所有结点都找不到有结点都找不到, ,即查找失败即查找失败顺序查找的优点是对线性表结点的逻辑次序无要求顺序查找的优点是对线性表结点的逻辑次序无要求, ,对线对线性表

29、的存储结构无要求性表的存储结构无要求, ,缺点是平均检索长度长缺点是平均检索长度长, ,为为n/2n/2要求线性表结点按关键字码值排好，且以顺序方式存储要求线性表结点按关键字码值排好，且以顺序方式存储用要查找的码值用要查找的码值X X与中间位置结点的关键码值与中间位置结点的关键码值W W相比较：相比较： (1) (1)X=WX=W，此时已经查找成功，查找结束。此时已经查找成功，查找结束。 (2) (2)XW,XW,表明表明X X在表的后半部分在表的后半部分, ,取后半部分进行查找取后半部分进行查找 (3) (3)XW,XW,表明表明X X在表的前半部分，取前半部分进行查找在表的前半部分，取前半

30、部分进行查找二分法查找的优点是平均检索长度小，为二分法查找的优点是平均检索长度小，为loglog2 2n n3.3.分块查找分块查找要求文件中记录关键字要求文件中记录关键字“分块有序分块有序”, ,即前一块中最即前一块中最大关键字小于后一块中最小关键字大关键字小于后一块中最小关键字, ,而块内的关键字而块内的关键字不一定有序不一定有序分块查找的分块查找的：先抽取各块中的最大关键字：先抽取各块中的最大关键字构成一个索引表，由于文件中的记录按关键字分块有构成一个索引表，由于文件中的记录按关键字分块有序，则索引表呈递增有序状态。查找分两步进行序，则索引表呈递增有序状态。查找分两步进行: :第第一步一

31、步先对索引表进行二分查找或顺序查找，以确定待先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块，查记录在哪一块，第二步第二步在已限定的那一块中进行顺在已限定的那一块中进行顺序查找序查找用分块查找的文件不一定分成大小相等的若干块，块用分块查找的文件不一定分成大小相等的若干块，块大小及其分法可根据文件的特征来定。分块查找不仅大小及其分法可根据文件的特征来定。分块查找不仅适用于顺序方式存储的顺序表，也适用于线性链表方适用于顺序方式存储的顺序表，也适用于线性链表方式存储的文件式存储的文件 3.4 排序3.4.1 基本概念 设含有设含有n n个记录的文件个记录的文件R R1 1，R R2 2，R

32、Rn n, ,其相应的关键其相应的关键字为字为K K1 1，K K2 2，K Kn n, ,需确定一种排列需确定一种排列P(1),P(2)P(1),P(2)P(n)P(n)使其相应的关键字满足递增使其相应的关键字满足递增( (或递减或递减) )关系：关系： K KP(1)P(1)KKP(2)P(2)K KP(n)P(n) 或或K KP(1)P(1)KKP(2)P(2)K KP(n)P(n) 使上述文件成为一个按其关键字线性有序的文件使上述文件成为一个按其关键字线性有序的文件R RP(1)P(1)，R RP(2)P(2) ，R RP(n)P(n)，这种运算就称为排序这种运算就称为排序内排序内排序

33、 指当文件的数据量不太大时，全部信息放在内存指当文件的数据量不太大时，全部信息放在内存中处理的排序方法。当文件的数据量较大时，排序过程中处理的排序方法。当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排中需要在内、外存之间不断地进行数据交换才能达到排序的目的，这种排序称为序的目的，这种排序称为外排序外排序3.4.2 插入排序基本思想是：基本思想是：每步将一个待排序的记录，按关键码值每步将一个待排序的记录，按关键码值的大小插入到前面已排序的适当位置上，直到全部的大小插入到前面已排序的适当位置上，直到全部插完止插完止1. 1. 直接插入排序：在排好的序列中用顺序法查找插

34、入直接插入排序：在排好的序列中用顺序法查找插入位置，找到后将其后记录后移一个位置，插入新记位置，找到后将其后记录后移一个位置，插入新记录。排序录。排序n n个记录的文件，关键码比较次数为个记录的文件，关键码比较次数为n n2 2量级，量级，记录移动个数也为记录移动个数也为n n2 2量级量级2. 2. 二分法插入排序：在已排好序的序列中使用二分法二分法插入排序：在已排好序的序列中使用二分法查找插入位置，找到后移动其后记录插入新记录。查找插入位置，找到后移动其后记录插入新记录。关键字比较次数降为关键字比较次数降为nlognlog2 2n n量级，记录移动个数仍量级，记录移动个数仍为为n n2 2

35、量级量级3.4.3 选择排序基本思想是：基本思想是：每次从待排序的记录中选出关键字最小每次从待排序的记录中选出关键字最小( (或最大或最大) )的记录，顺序放在已排序的记录序列的最后，的记录，顺序放在已排序的记录序列的最后，直到全部排完为止直到全部排完为止基本思想是：基本思想是：两两比较待排序记录的关键码，并交换不两两比较待排序记录的关键码，并交换不满足顺序要求的偶对，直至全部满足为止满足顺序要求的偶对，直至全部满足为止1.1.起泡排序：将待排序的记录按从后向前的顺序顺次两起泡排序：将待排序的记录按从后向前的顺序顺次两两比较，若为逆序则进行交换。将序列照此两比较，若为逆序则进行交换。将序列照此 方法从方法从头到尾处理一遍称作一趟起泡，一趟起泡的效果是将头到尾处理一遍称作一趟起泡，一趟起泡的效果是将关键码值最小的记录交换到了最前位置，即该记录的关键码值最小的记录交换到了最前位置，即该记录的顺序起始位置。若某一趟起泡过程中没有任何交换发顺序起始位置。若某一趟起泡过程中没有任何交换发生，则排序过程结束生，则排序过程结束对对n n个记录的文件进行排序。所需执行时间是个记录的文件进行排序。所需执行时间是n n2 2量级