大学计算机基础（第6版）（微课版） 课件 第6章 算法与数据结构

第6章算法与数据结构大学计算机基础课程组2022年4月程序数据结构=算法+主要内容算法的基本知识1数据结构基础2几种常见的算法33主要内容1算法及其基本特点算法描述方法算法复杂度分析数据结构基础2几种常见的算法34算法的基本知识数据结构的概念常见的几种数据结构及其基本操查找算法、排序算法、递推算法、枚举算法、贪心算法、分治算法算法(algorithms):是为了求解问题而给出的有限的指令序列，每条指令表示一个或多个操作。——解决问题的步骤程序是算法的一种实现，计算机按照程序逐步执行算法，实现对问题的求解。6.1算法（algorithm）基础方案设计方案实现数据模型基本想法数据表示数据处理选择语言选择IDE方法设计6.1.1计算机求解问题的过程6.1.2算法的特点有穷性：一个算法必须能在执行有穷步之后结束，且每一步都可在有穷时间内完成；确定性：算法中每一条指令必须有确切的含义，不具有二义性。可行性：算法中描述的操作都可通过已经实现的基本运算执行有限次来实现。输入：一个算法有零个或多个输入，这些输入取自某个特定的对象的集合输出：一个算法有一个或多个输出，这些输出是同输入具有某种特定关系的量。算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。常用的描述算法的方法有自然语言流程图程序设计语言伪代码等。下面以计算10个数的平均值算法为例进行介绍6.1.3算法的描述方法自然语言（1）定义一个变量sum用来记录10个数的和，并给其赋值为0。（2）输入一个数x，并将输入的这个数x与sum进行加法计算，用sum记录加法计算的结果。（3）重复执行（2）10次。第1次执行（2）时sum中记录了第1个数的值，第2次执行（2）后sum中记录了前2个数的和，第3次执行（2）后sum中记录了前3个数的和……，第10次执行（2）后sum中记录下了10个数的和。（4）将sum除以10，得到10个数的平均值。用自然语言描述算法，最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长流程图用流程图描述算法，优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言程序设计语言用程序设计语言描述的算法能由计算机直接执行，而缺点是抽象性差.#include<stdio.h>intmain(){floatsum=0,x; inti=1; while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}伪代码伪代码是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。（1）sum=0,i=1;（2）如果i<=10,则执行下面操作，否则，转（3）。

①输入x;

②sum=sum+x;

③i=i+1;

④转（2），继续执行（3）输出sum/10.6.1.4算法复杂度分析解决同一个问题总是存在着多种算法，而算法设计者在所花费的时间和所使用的空间资源往往要两者之间采取折中。算法设计者可以通过算法分析，判断所提出的算法是否现实，分析算法的效率以求改进。算法分析的内容算法运行所需要的时间，称为时间复杂性算法运行所需要的辅助空间，称为空间复杂性撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模n，即输入量的大小。如： 对一个长度是n一维数组排序，问题规模为n

对一个m*n的二维数组进行排序，问题规模为m*n算法执行时间T是问题规模的函数，计为T(n).

算法时间复杂度分析算法的时间复杂度估计主要评估n逐步增大时，T(n)的增长趋势#include<stdio.h>intmain(){

floatsum=0,x; inti=1,n;

scanf("%d”,&n);while(i<=10){ scanf("%f",&x); sum=sum+x i=i+1; } printf("%f",sum/10); return0;}

n程序的执行时间:∑语句i的执行次数×执行时间

i=1(=1)语句频度:语句重复执行的次数计算机执行简单操作的时间，可认为是常量。nnnn11时间复杂度：

算法的执行时间(所有语句的语句频度之和）T(n)=1+n+n+n+n+1=2+4n问题规模：求解问题的输入量

limT(n)/n=lim(2+4n)/n=1n－>∞当问题规模n→∞时T(n)与某一量同阶,称作算法的渐近时间复杂度（asymptotictimecomplexity，随着问题规模的增加，算法运行时间的增长趋势）

：记作：T(n)=O(n)O是order的简写例2:算法的时间复杂度分析intcount=0;

O(1)O(n)count=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)count++;O(n2)intn=8,count=0,i;for(i=1;i<=n;i++)count++;常见的时间复杂度量级有常数阶O(1)（算法执行时间是一个与问题规模无关的常数）、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n²)、立方阶O(n³)、K次方阶O(nk)、指数阶O(2n)等等。算法的空间复杂度算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。通常记作：S(n)=O(f(n))其中，n为问题规模，分析方法与算法的时间复杂度类似。辅助空间的统计将数组a中的元素逆置方法一：intx;for(i=0;i<n/2;i++) x=a[i];a[i]=a[n-i];a[n-i]=x;方法二：intb[]for(i=0;i<n;i++)b[i]=a[n-i];for(i=0;i<n;i++)a[i]=b[i];需要一个辅助空间，O(1)需要年n个辅助空间，O(n)6.2数据结构基础用计算机求解问题一般包含两个步骤：⑴抽象出问题的模型；⑵求该模型的解。对于数值问题抽象出的模型通常是数学方程，例如图形的面积与周长等预报人口增长情况的模型更多的非数值问题是难以用数学方程来描述的。数值计算问题实例：计算课程平均成绩学号姓名班级性别课程成绩2021001韩华计算机21-1女832021002刘明计算机21-1男802021003刘茜计算机21-1女902021004王艺计算机21-1男75大学计算机课程成绩表要完成平均成绩的计算，需要将所有同学的考试成绩加起来，然后除以学生总人数，即可得到该门课程的平成绩。该问题属于数值计算问题非数值计算问题实例：确定学生名次学号姓名班级性别课程成绩2021001韩华计算机21-1女832021002刘明计算机21-1男802021003刘茜计算机21-1女902021004王艺计算机21-1男75大学计算机课程成绩表要排出名次，需要按照考试成绩对表中数据进行降序排序。该操作不会修改表中数据的值，只会改变表中数据的排列顺序。这类问题不能通过设计一个数学模型的方式来解决，属于非数值计算问题非数值计算问题实例：微信联系人管理6.2.2数据结构的几个基本概念数据（Data）:是对客观事物的符号表示，在计算机科学中是指能输入到计算机并被计算机程序处理的符号的总称。数据元素（DataElement）:是数据的基本单位，也可以称为结点，在计算机程序中通常作为一个整体进行考虑。数据项（DataItem）：数据元素一般由若干数据项组成，数据项是构成数据元素最小的、不可分割的单位。数据结构（DataStructure）:

相互之间存在一定关系的数据的集合。 是数据及其元素之间相互关系的表示。逻辑结构：数据元素之间一般存在某种特定的关系，这种关系称为数据的逻辑结构。物理结构（存储结构）：数据结构在计算机内存中的表示形式。包括数据元素的表示和其关系的表示。逻辑结构线性结构（linearstructure）树型结构（treestructure）图结构（graphstructure）集合（set）线性结构实例学号姓名班级性别课程成绩2021001韩华计算机21-1女832021002刘明计算机21-1男802021003刘茜计算机21-1女902021004王艺计算机21-1男75线性关系具有以下特点：（1）有且仅有一个开始结点和一个终端结点（注：一个结点即为一个数据元素）。（2）其余所有结点都只有一个直接前驱和一个直接后继。树结构：树结构具有以下特点：（1）只有一个结点没有直接前驱。（2）可以有多个结点没有直接后继。（3）树中的每个结点，如果有直接前驱，直接前驱只有一个；如果有直接后继，直接后继可以有多个。图结构在图结构中一个结点可以有0个或多个直接前驱和直接后继。ABDCAEDCBDACBE树状结构图或网状结构CBDA集合线性结构数据的存储结构计算机的主存储器的特性其存储空间提供了一种具有非负整数地址编码的，相邻单元的集合，其基本的存储单元是字节计算机的指令具有按地址随机访问存储空间内任意单元的能力，访问不同地址所需的访问时间基本相同数据的存储结构又称物理结构，是数据及其逻辑结构在计算机中的表示存储结构的分类：1.顺序结构 2.链式结构顺序（sequential）存储用一块无空隙的存储区域存储数据称为顺序存储顺序存储把一组结点存储在按地址相邻的顺序存储单元里，结点间的逻辑后继关系用存储单元的自然顺序关系来表达链式（linked）存储ABCF

DE6.2.5几种常见的数据结构线性表栈队列二叉树线性表及其基本操作由0个或多个具有线性逻辑关系的数据元素组成的一个有限序列称为线性表(LinearList)。可以采用下面的通用形式描述一个线表：L=（a1,a2,a3,……,an）在上述形式化的描述中,ai代表一个数据元素，下标i代表数据元素在线性表中的编号。可以采用顺序存储结构或链式存储结构存储一个线性表顺序表采用顺序存储结构存储的线性表称为顺序表。顺序存储是利用一维数组实现的。顺序表中查找第i个数据元素根据顺序存储的特点，可以直接利用顺序表中第一个数据元素的地址（用loc(a1)表示），计算出顺序表中第i个数据元素的地址（用loc(ai)表示）,计算公式见公式（1）：loc(ai)=loc(a1)+(i-1)*c （公式1）公式（1）中的c是一个整数，表示每个数据元素所占内存大小。算法的时间复杂度为O(1)。顺序表中插入第i个数据元素插入操作是指在长度为n的顺序表中插入一个数据元素，插入之后顺序表的长度变为n+1。时间复杂度为O(n)顺序表中删除第i个数据元素删除操作是指在长度是n的顺序表中删除一个数据元素，删除之后顺序表的长度变为n-1。删除操作可以按位置删除，也可以按值删除。按位置删除时，需要指明删除的位置；按值删除时，需要查找要删除的元素在顺序表中的位置，之后再进行删除。时间复杂度为O(n)单链表及基本操作单链表中查找第i个数据元素利用工作指针移动的次数评估算法的时间复杂度。分析这一查找过程可以看到，查找操作所需要移动指针的次数与单链表的长度成正比该查找算法的时间复杂度为度为O(n)单链表中插入第i个数据元素单链中第5个元素的位置上插入88时间复杂度也为O(n)单链表中删除第i个数据元素单链中删除第5个元素的操作过程。时间复杂度也为O(n)双链表可以采用双链表存储一个线性表。在双链表中，每个结点既存储了后继结点的地址，又存储了其前驱结点的地址。双链表中插入第i个数据元素时间复杂度为O(n)双链表中删除第i个数据元素时间复杂度为O(n)栈是仅允许在线性表的同一端进行插入或删除操作的线性表允许插入或删除操作的这一端称为栈顶,另一端称为栈底栈具有FILO（FirstInLastOut）的特点。a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的操作特性：后进先出a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈的示意图例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况1：栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况2：队列空队列：不含任何数据元素的队列。

队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。（a1,a2,……,an）队尾队头a1a2a3入队队尾队头出队队头队列的操作特性：先进先出(FIFO,LILO)二叉树二叉树中包含n(n>=0)个结点。n为0时，二叉树是一棵空树。非空的二叉树中包含一个树根；除根结点外，其余的结点分为两个互不相交的子集，分别称为根结点的左子树和右子树。二叉树的基本形态Ф空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树结点的度：结点所拥有的子树的个数。叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。特殊的二叉树斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。

斜树的特点：ABCABC满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。满二叉树的特点：叶子只能出现在最下一层；只有度为0和度为2的结点。特殊的二叉树CDEFGHIJKLMNO1112131415满二叉树不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多A1523467BCDEFGLM89特殊的二叉树完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。特殊的二叉树CDEFGHIJKLMNO1112131415CDEFGHIJ在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点特殊的二叉树1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。

3.深度为k的完全二叉树在k-1层上一定是满二叉树。完全二叉树的特点CDEFGHIJ性质1：二叉树的第k层最多有2k-1个结点。性质2：深度为k的二叉树中最多有2k-1个结点；最少有k个结点。性质3：在一棵二叉树中，度为0的结点个数比度为2的结点个数多一个。性质4：含有n个结点的完全二叉树的高度为log2n。性质5：完全二叉树中编号是i的结点，如果有左儿，左儿子的编号是2×i，如果有右儿子，右儿子的编号是2×i+1；如果有父亲，父亲编号是i/2。【性质1】在二叉树的第k层上最多有2k-1个结点（k≥1）ABCDFEHG【性质2】深度为m的二叉树最多有2m-1个结点（m≥1）A1523467910BCDEFGHIJK11L12M13N14O158【性质3】在任意一棵二叉树中，若度为0的结点（即叶子结点）的个数为n0，度为2的结点数为n2，则n0=n2+1。

ABCDFEHG度为2的结点叶子结点性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。

证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：

n＝n0＋n1＋n2

在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：

n＝n1＋2n2＋1因此可以得到：n0＝n2＋1。在有n个结点的满二叉树中，有多少个叶子结点？因为在满二叉树中没有度为1的结点，只有度为0的叶子结点和度为2的分支结点，所以，n＝n0+n2n0＝n2+1

即叶子结点n0＝（n+1）/2

性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。

性质4：具有n个结点的完全二叉树的深度为log2n+1。

证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1层———第k层…最少结点数最多结点数

证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立

2k-1≤n＜2k性质4：具有n个结点的完全二叉树的深度为log2n+1。

对不等式取对数，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整数，故必有k＝log2n+1。

性质5：对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1≤i≤n）的结点（简称为结点i），有：

（1）如果i＞1， 则结点i的双亲结点的序号为

i/2；如果i＝1， 则结点i是根结点，无双亲结点。(2)如果2i≤n， 则结点i的左孩子的序号为2i； 如果2i＞n，则结点i无左孩子。(3)如果2i＋1≤n， 则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点

i无右孩子。

可以用归纳法证明其中的（2）和（3）：当i=1时，结论成立123(2)如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。

(3)如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点i无右孩子。假设：对于序号为j(1≤j≤i)的结点，当2×j≤n时，其左孩子存在且序号为2×j，当2×j>n时，其左孩子不存在；当2×j+1≤n时，其右孩子存在且序号为2×j+1，当2×j+1>n时，其右孩子不存在。(2)如果2i≤n，则结点i的左孩子的序号为2i；如果2i＞n，则结点i无左孩子。

(3)如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；如果2i＋1＞n，则结点i无右孩子。j2j2j+1当i=j+1时，根据完全二叉树的定义，若其左孩子存在，其左孩子结点的序号等于=2×i，且有2×i≤n；如果2×i>n，则左孩子不存在。若右孩子结点存在，右孩子结点的序号为2×i+1，且有2×i+1≤n；如果2×i+1>n，则右孩子不存在。故（2）和（3）得证。j2j2j+1i=j+12i2i+1由（2）和（3）我们可以很容易证明（1）。如果i＝1，则结点i是根结点，无双亲结点。如果i＞1，则结点i的双亲结点的序号为

[i/2]；

i2i2i+1118910456723对一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为

i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。

性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。二叉树的遍历操作

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD层序遍历：按二叉树的层序编号的次序访问各结点。

考虑二叉树的组成：根结点D左子树L右子树R二叉树前序（根）遍历若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树。前序遍历序列：ABDGCEFABCDEFG中序（根）遍历若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。

中序遍历序列：DGBAECFABCDEFG后序（根）遍历若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点；后序遍历序列：GDBEFCAABCDEFG层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

层序遍历序列：ABCDEFGABCDEFG--/+*abcdef二叉树遍历操作练习前序遍历结果：-+a*b-cd/ef中序遍历结果：a+b*c-d-e/f后序遍历结果：abcd-*+ef/-6.3常见的几种算法查找算法排序算法枚举、递推、贪心、分治等算法查找算法顺序查找算法折半查找算法顺序查找是指从数组的一端开始，依次将要查找的数据元素与数组中的数据元素进行比较的过程。折半查找在有序表中（low,high,low<=high），取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。折半查找的基本思想

[r1………rmid-1]rmid[rmid+1………rn]

如果k<rmid

如果k>rmid查找左半区查找右半区k（mid=(1+n)/2）例：查找值为14的记录的过程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值为22的记录的过程：

012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>high排序：给定一组记录的集合{r1,r2,……,rn}，其相应的关键码分别为{k1,k2,……,kn}，排序是将这些记录排列成顺序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。正序：待排序序列中的记录已按关键码排好序。逆序（反序）：待排序序列中记录的排列顺序与排好序的顺序正好相反。趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。 通常，一次排序过程需要进行多趟扫描才能完成排序的基本概念排序的分类-根据排序过程中所进行的基本操作分：1.基于比较：基本操作——关键码的比较和记录的移动，其最差时间下限已经被证明为O（nlog2n）。2.

不基于比较：根据关键码的分布特征。比如，桶式排序，基数排序（多关键字排序）排序的基本概念基于比较的内排序1.插入排序2.交换排序3.选择排序4.归并排序不基于比较的内排序1.分配排序 桶式排序 基数排序时间复杂性：基本操作。内排序在排序过程中的基本操作：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.空间复杂性：

辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。排序算法的性能基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。直接插入排序有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?直接插入排序需解决的关键问题?直接插入排序过程示例

r0123456211825221025*212125i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5直接插入排序算法性能分析最好情况下（正序）：

12345时间复杂度为O(n)。比较次数：n-1移动次数：2(n-1)123451234512345123452345直接插入排序算法性能分析最好情况下（正序）：

比较次数：n-1移动次数：2(n-1)最坏情况下（逆序或反序）：时间复杂度为O(n2)。54321453213452123451123454321比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(4(1-+=+ånnin2=i）（时间复杂度为O(n)。平均情况下（随机排列）：

直接插入排序算法性能分析时间复杂度为O(n2)。比较次数：移动次数：4)1)(4(-+=ånnn2=i4)1)(2(2-+=å=nnnii2（21+i）交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。

交换排序反序则交换rirj交换类排序的两种方法冒泡排序快速排序起泡排序基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

rj

rj+1ri+1≤……

≤rn-1≤rn

无序区有序区1≤j≤i-1已经位于最终位置反序则交换05981269385381起泡排序过程示例

059812693853810598126938538105981269385381起泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：012345时间复杂度为O(n)。12345最坏情况（反序）：起泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：054321时间复杂度为O(n)；时间复杂度为O(n2)。43215321452134512345比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i平均情况：时间复杂度为O(n2)。选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。

有序序列r1r2ri-1rirnrk…………无序序列rnri+1r1r2ri-1……riri……交换最小记录选择排序简单选择排序示例0821i=2最小者08交换21,08最小者16交换25,16最小者21交换49,212128i=12516490808i=3210828492128491625161625i=4最小者25交换25,28i=5最小者28不交换简单选择排序示例492108281625254921081628252849210816282528无序区只有一个记录归并排序归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。

归并排序归并：将两个或两个以上的有序序列合并成一个有序序列的过程。二路归并排序60203154455652060531445565

60203154455655203160

4455655203144556065二路归并排序算法的性能分析时间性能：一趟归并操作是将r[1]~r[n]中相邻的长度为h的有序序列进行两两归并，并把结果存放到r1[1]~r1[n]中，这需要O(n)时间。整个归并排序需要进行趟，因此，总的时间代价是O(nlog2n)。这是归并排序算法的最好、最坏、平均的时间性能。空间性能：算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为O(n)。éùn2log桶式排序假设待排序的记录的值在0~m-1之间设置m个桶，依次扫描待排序的记录，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

3151321526338分/p>

680123456789收集1313233515268桶式排序分析特点：需要较多的桶时间复杂性一次分配，O(n)一次收集，O(m)O(n+m)空间复杂性O(m)基数排序每张扑克牌有两个“关键码”：花色和面值。其有序关系为：

花色：

面值：2

<3<4<5<6<7<8<9<10<J<Q<K<A基数排序“花色”优先及高于“面值”方法一：先按花色分成4堆；然后，每堆再按“面值”排；最后，收成一堆。

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K“花色”优先及高于“面值”方法二？ 先按面值分成13堆；收成一堆。再按花色分成四堆，最后，收成一堆。A

2

3

4

5

6

7

8

9

10

J

Q

K

1,2,3…K

1,2,3…K

1,2,3…K

1,2,3…K基数排序基数排序（低位优先）基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。基本思想从关键字的最“低位”开始，将关键字分配到r(基数）个堆（桶）中；按桶的编号将关键字收集起来；然后，以“次低位”将关键字又分配到r个桶中；再收集，……，重复直到“