算法和数据结构

程序设计=计算机编程语言+数据结构+算法数据结构是指数据的逻辑结构和存储结构，而算法则是对数据运算的描述。程序设计的实质是对实际问题选择一种好的数据结构，加之设计一个好的算法。第1页，课件共79页，创作于2023年2月算法的定义算法的要素算法的表示算法与计算机程序的关系算法设计的基本方法对算法的评价第2页，课件共79页，创作于2023年2月算法的定义

一组明确的可执行步骤的有序集合例：输入两个正整数m和n(m>n),求它们的最大公约数,记为god(m,n)。根据欧几里德算法：若r是m÷n的余数,则gcd(m,n)=gcd(n,r)第3页，课件共79页，创作于2023年2月适合计算机实现的算法(辗转相除法)：如m=28,n=8,则god(28,8)=god(8,4)=god(4,0)=4算法描述自然语言：输入m,n(m>n)；求m/n的余数r；如果r≠0则将n放入m，r放入n，转第2步继续；如果r=0则转第4步输出最大公约数n。第4页，课件共79页，创作于2023年2月开始mmodn→rn→mr→n是否结束打印n输入m,nr=0?流程图：第5页，课件共79页，创作于2023年2月算法的特征有穷性（finiteness）--能在有限时间内做完；确定性（definiteness）--每一步骤都有明确定义；可行性（effectiveness）--能实现和达到预期目的；信息性（information）--能提供足够的情报，具有输入、输出。算法的要素精确,简单和抽象分级第6页，课件共79页，创作于2023年2月算法的表示流程图N-S图伪码程序流程图 N－S图

伪码第7页，课件共79页，创作于2023年2月算法与计算机程序算法是逻辑步骤计算机程序是使用某种编程语言表达算法第8页，课件共79页，创作于2023年2月算法设计的基本方法列举法---根据提出的问题列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，而哪些是不需要的；递推法---从已知的初始条件出发，逐次地推出所要求的各中间结果和最后结果；减半递推法---工程上常用的分治法，即将问题的规模减半来解，最后重复“减半”的过程；第9页，课件共79页，创作于2023年2月递归法

---首先将问题逐层分解最后归结为一些最简单的问题，解决这些最简单问题后再沿着原来分解的逆过程逐步进行综合。回溯法---在处理复杂数据结构时，通过对问题的分析找出一个解决问题的线索，然后沿着次线索逐步试探，若失败就逐步回退并换别的路线再进行试探；归纳法---通过列举足够多的特殊情况发现其中一些规律，经过分析最终找出一般的关系；第10页，课件共79页，创作于2023年2月算法举例第11页，课件共79页，创作于2023年2月输入一个数maxn=2当n<=10成立输入一个数xx>maxymax=xn=n+1输出其中的最大值max

输入十个数，找出最大数输出（递推法）第12页，课件共79页，创作于2023年2月假定一对刚出生的小兔子，一个月后就能长成大兔子，再过一个月后就开始生小兔子，并且也正好生一对兔子。问在没有兔子死亡的情况下，一对初生的兔子一年后可繁殖成多少对兔子。（递推法）解：用F(n)表示第n个月的兔子对数。第一个月：F(1)=1第二个月：F(2)=F(1)+0=1第三个月：F(3)=F(2)+1=2第四个月：F(4)=F(3)+1=3第五个月：F(5)=F(4)+2=5第六个月：F(6)=F(5)+3=8第七个月：F(7)=F(6)+5=13第13页，课件共79页，创作于2023年2月递推到一年后即第十三个月，得Fibonacci数列：1，1，2，3，5，8，13，21，34，55，89，144，233分析可知：第n个月的兔子对数由两部分组成：一是第n-1

个月的兔子对数；二是第n-2

个月的兔子对数所以得递推关系为

F(1)=1F(2)=1…

F(n)=F(n-1)+F(n-2)n=3,4,…第14页，课件共79页，创作于2023年2月求Fibonacci数列流程图开始F1=1,F2=1,n=3n<14F3=F1+F2

F1=F2,F2=F3n=n+1输出Fn结束NY第15页，课件共79页，创作于2023年2月设每只母鸡值3元，每只公鸡值2元，每只小鸡值0.5元。现要用100元钱买100只鸡，设计买鸡方案算法。（列举法）解：设买母鸡I只，买公鸡J只，买小鸡K只，则有第16页，课件共79页，创作于2023年2月猴子吃桃子：小猴在一天摘了若干个桃子，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第7天早上要吃时只剩下一个了，问小猴那天共摘下了多少个桃子？设第n天的桃子为Ｘn，那么它是前一天的桃子数Ｘn-1的二分之一减一。递推关系为：

第7天：1第6天：4第5天：10第4天：22第3天：46第2天：94第1天：190第17页，课件共79页，创作于2023年2月猴子吃桃子算法的流程图i>1i=i-1x=xixi=2(x+1)输出i,xii=7,x=1结束NY开始第7天：1第6天：4第5天：10第4天：22第3天：46第2天：94第1天：190第18页，课件共79页，创作于2023年2月0f(x1)f(x2)f(x3)f(x4)x1x2x3x4减半递推（迭代）法设方程f(x)=0在区间[x1,x2]上有一个实根，且f(x1)与f(x2)异号，用二分法求该方程在区间[x1,x2]上的实根。减半递推过程：求中点：x3=1/2(x1+x2)判f(x3)是否接近0？若接近0，x3即为所求根若不接近0，则将原区间减半舍弃与f(x3)同号者：x2=x3

再求中点：x4=1/2(x1+x3)如此重复得：x1,x2,…,xn-1,xn当xn与xn-1之差小于给定的误差En时，xn即为近似解迭代关系：x3=(x1+x2)/2舍弃与f(x3)同号者：f(x3)*f(x2)>0:x2=x3;/*为下一次迭代做准备*/f(x3)*f(x1)>0:x1=x3;第19页，课件共79页，创作于2023年2月f(x3)*f(x1)<0f(x3)=..f(x1)=..f(x2)=...x1=x3x2=x3输入x1,x2结束NY开始x3=(x1+x2)/2|f(x3)|>10-4输出结果x3YN流程图第20页，课件共79页，创作于2023年2月算法的评价时间复杂度：指算法中包含简单操作的次数假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度一般以数量级的形式给出如Ο(1),Ο(log2n),Ο(n),Ο(n2)其中Ο(1)表示算法的时间复杂度为常量，它不随数据量n的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为Ο(1)第21页，课件共79页，创作于2023年2月Fori=1ton－1do{y=y+1;/*①*/Forj=0to2ndox=x+1;/*②*/}语句①的执行次数为：n－1，语句②的执行次数为：（n－1）（2n＋1）＝2n2－n－1该程序段的时间复杂度为：T（n）＝O（n－1＋2n2－n－1）＝O（n2）第22页，课件共79页，创作于2023年2月空间复杂度空间复杂度主要考虑在算法运行过程中临时占用的存储空间的大小假如，随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同，则可记作：S(n)=O(g(n))称S(n)为算法的空间复杂度第23页，课件共79页，创作于2023年2月数据结构的基本术语数据的逻辑结构数据的存储结构第24页，课件共79页，创作于2023年2月基本术语数据：信息的载体，它能够被计算机识别、存储和加工处理。数据元素：是数据的基本单位。数据项：具有独立意义的最小数据单位，是对数据元素属性的描述，也称域或字段。数据对象：指具有相同性质的数据元素的集合，是数据的一个子集。数据处理：指对数据集合中的各元素，以各种方式进行处理，包括对数据的插入、删除、查找、更新、排序等基本运算，也包括对数据元素进行分析。第25页，课件共79页，创作于2023年2月数据结构的定义：互相有关联的数据元素的集合一个数据结构应包含两方面信息：所有数据元素的信息各数据元素之间的关系第26页，课件共79页，创作于2023年2月数据结构研究的内容数据集合中，各种数据元素之间所固有的逻辑关系，即数据的逻辑结构。在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。对各种数据结构进行的运算，其中常用的有检索、插入、删除、排序等。第27页，课件共79页，创作于2023年2月数据的逻辑结构--反映数据元素之间的逻辑关系一个数据结构可以表示为一个二元组：B=（D，R）D是数据元素的集合，R是定义在D上的二元关系的集合，反映了D中各元素之间的前驱与后继关系二个要素数据元素的集合DD上的二元关系R举例第28页，课件共79页，创作于2023年2月例1.一年四季的数据结构。

表示为：Season=（D，R）

D=（春，夏，秋，冬）

R=（（春，夏），（夏，秋），（秋，冬））例2.n维向量X=（x1，x2，……，xn）的数据结构。

表示为：X=（D，R）

D=（x1，x2，……，xn）

R=（（x1，x2），（x2，x3）…，（xn-1，xn））例3.家庭成员的数据结构。

表示为：Family=（D，R）

D=（父亲，儿子，女儿）

R=（（父亲，儿子），（父亲，女儿））第29页，课件共79页，创作于2023年2月根据数据结构中各数据元素之间的前驱与后继关系的复杂程度，逻辑上可以把数据结构分为线性结构和非线性结构。一个非空的线性数据结构应满足两个条件：有且仅有一个根结点（没有前驱的结点）；每一个结点最多只有一个前驱，一个后继；如果一个数据结构不是线性的，则称为非线性结构（树形结构、图形结构或网状结构）。例1、例2属于线性结构，例3为非线性结构。第30页，课件共79页，创作于2023年2月三种基本结构图示线性结构：元素之间是一对一的关系树形结构：元素之间是一对多的关系(非线性)

图形结构或网状结构：元素之间是多对多的关系(非线性)

第31页，课件共79页，创作于2023年2月数据的存储结构：即数据的逻辑结构在计算机存 储空间中的存放形式常见四种：顺序存储结构链式存储结构索引存储结构散列存储结构第32页，课件共79页，创作于2023年2月线性表的基本概念线性表的顺序存储及其运算线性表的链式存储及其运算第33页，课件共79页，创作于2023年2月线性表的基本概念线性表是由n（n>=0）个元素a1，a2，…，an组成的有限序列，记为：（a1，a2，…，an）。数据元素（也称为结点）的个数n称为线性表的长度，n=0时称此线性表为空表。非空线性表（a1,a2,…,an）的结构特征：若线性表非空，第一个元素无前驱；最后一个元素无后继；其他元素仅有一个直接前驱和一个直接后继。第34页，课件共79页，创作于2023年2月线性表的顺序存储及其运算线性表的顺序存储所有元素所占的存储空间连续各数据元素在存储空间中按逻辑顺序依次存放ADR(ai)=ADR(a1)+(i-1)k第35页，课件共79页，创作于2023年2月顺序表的基本运算顺序表的插入长度为n的顺序表（a1,a2,…,ai,…,an），在第i个元素之前插入一个新元素x，插入后得到长度为n+1的顺序表（a1,a2,…,x,ai,…,an）算法：从an到ai,依次后移，然后插入x线性表的删除

将表的第i（1≤i≤n）个结点删去，使长度为n的线性表（a1，…，ai-1，ai，ai+1，…，an）变成长度为n-1的线性表（a1，…，ai-1，ai+1，…，an）算法：从ai+1到an,依次前移第36页，课件共79页，创作于2023年2月线性表的顺序存储结构具有简单、存储密度大、空间利用率高、对表中任一元素可直接确定其存储地址（随机存取）、效率高等优点；但是也有明显的不足：在顺序表中进行插入与删除等操作时，需大量移动数据元素，浪费时间。对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用链式存储结构。第37页，课件共79页，创作于2023年2月线性表的链式存储及其运算链式存储一个链表结点由两个域构成：数据域和指针域数据域存放数据元素值指针域指向该结点的后继结点通过每个结点的指针域将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。用一个头指针专门用来指向线性链表中的第一个结点，线性链表中最后一个元素没有后继，指针域为空（用NULL或0表示）。第38页，课件共79页，创作于2023年2月线性链表的物理存储状态线性链表的逻辑存储状态第39页，课件共79页，创作于2023年2月单链表的基本运算单链表的结点插入算法：（1）找到ai-1存储位置p（2）确定要插入的新结点的位置s（3）在新结点的数据域中输入x（4）新结点的指针域指向结点ai。（5）结点p的指针域指向新结点第40页，课件共79页，创作于2023年2月单链表的结点删除算法：

（1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域中）（2）找到ai的存储位置r（3）令p的指针域指向ai的直接后继结点（即把ai从链上摘下）（4）释放结点ai的空间，将其归还给"存储池"。第41页，课件共79页，创作于2023年2月栈及其基本运算队列及其基本运算第42页，课件共79页，创作于2023年2月栈及其基本运算定义：堆栈（Stack）可以看成是一种“特殊的”线性表，这种线性表上的插入和删除运算限定在表的某一端进行的。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出的线性表，简称为LIFO表。

栈的示意图第43页，课件共79页，创作于2023年2月栈的顺序存储及其运算利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常，栈底指针指向栈空间的低地址一端入栈运算首先将栈顶指针加1（即top加1）然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈的“上溢”。上溢是一种出错状态，应设法避免。

第44页，课件共79页，创作于2023年2月栈在顺序存储结构下的运算第45页，课件共79页，创作于2023年2月退栈运算首先将栈顶元素（即栈顶指针指向的元素）赋给一个指定的变量然后将栈顶指针减1（即top减1）。当栈顶指针为0时，说明栈空，不可能进行退栈运算。这种情况称为栈的“下溢”错误。读栈顶运算读栈顶元素是指将栈顶元素赋给一个指定的变量。在这个运算中，栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。第46页，课件共79页，创作于2023年2月队列及其基本运算定义：是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头（Front），允许插入的一端称为队尾（Rear）。队列亦称作先进先出的线性表，简称为FIFO表。具有7个元素的队列示意图第47页，课件共79页，创作于2023年2月插入和删除队列元素示意图入队运算首先将新元素插入到队尾指针指向的位置，然后将队尾指针加1（即rear＋1）出队运算首先将队首指针指向的元素赋给指定的变量，然后将队首指针加1（即front＋1）第48页，课件共79页，创作于2023年2月循环队列及其运算循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间初始状态为空：rear=front当队列满了，也有：rear=front，需要一个标志变量s循环队列存储空间示意图第49页，课件共79页，创作于2023年2月循环队列出队运算首先将队首指针指向的元素赋给指定的变量，然后将队首指针加1（即front＋1），并当front＝m＋1时置front＝1，这时如果front＝rear，则说明队空，应将s置0。当循环队列为空时，不能进行出队运算，这种情况称为“下溢”。循环队列及其删除运算示意图第50页，课件共79页，创作于2023年2月循环队列入队运算首先将新元素插入到队尾指针指向的位置，然后将队尾指针加1（即rear＋1），当rear＝m＋1时置rear＝1，这时如果s＝0，则置s＝1，表示队列非空。当循环队列非空（即s＝1）且font＝rear时，说明循环队列已满，不能进行入队运算，这种情况称为“上溢”。循环队列及其插入除运算示意图第51页，课件共79页，创作于2023年2月树的基本概念二叉树及其基本性质二叉树的存储结构二叉树的遍历第52页，课件共79页，创作于2023年2月树型结构是以分支关系定义的层次结构，是一种重要的非线性结构。基本概念定义：树是n个结点的有限集T，具有明显的层次结构。其中：一个特定的结点称为该树的根（root）结点;结点之外的其余结点可分为m（m≥0）个互不相交的有限集合T1,T2,......,Tm，且其中每一个集合本身又是一棵树，称之为根的子树（subtree）。只有根结点的树AHGFBEDCAKMJIL一般的树第53页，课件共79页，创作于2023年2月基本术语结点的度树的度叶子分支结点双亲和孩子结点的层树的深度兄弟和堂兄弟祖先和子孙有序树和无序树森林HGFBEDCAKMJIL树的图形表示结点的度：一个结点的子树数目。结点A的度：3结点C的度：1结点M的度：0树的度：所有结点中最大的度。树的度：3叶子：树中度为0的结点。叶子：E,K,L,G,H,M,J分支结点：树中度不为0的结点。分支结点：A,B,F,C,D,I双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子结点的双亲结点A是B,C,D的双亲，B,C,D是结点A的孩子结点的层：约定树的根节点的层为1，其余结点的层是其双亲的层加1结点A的层：1结点B,C,D的层：2结点E,F,G的层：3树的深度：树中各结点的层的最大值。图中的树的深度：4兄弟和堂兄弟：同一双亲的结点互称为兄弟，其双亲在同一层但不属于同一双亲的结点互称为堂兄弟。结点E,F,G是兄弟，G,H,I是堂兄弟祖先和子孙：一个结点的祖先是指从该结点到树根所经分支上的所有结点。一个结点的子树上的所有结点称为该结点的子孙。E的祖先有A和B，而E、F、G、K、L是B的子孙。有序树和无序树：如果树中任一结点的各颗子树规定从左至右是有序的，即不能互换位置，则称该树为有序树，否则称为无序树。森林：n（n≥0）棵互不相交的树的集合称为森林。删去一棵树的根结点便得到一个森林；反过来，给一个森林加上一个结点，使原森林的各棵树成为所加结点的子树，便得到一棵树。第54页，课件共79页，创作于2023年2月

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树的定义定义：二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。第55页，课件共79页，创作于2023年2月NLR空树只含根结点NNN右子树为空树左子树为空树左右子树均不为空树二叉树的五种基本形态：LR第56页，课件共79页，创作于2023年2月二叉树的基本性质性质1在二叉树的第i层至多有2i-1个结点(i≥1)性质2深度为k(k≥1)的二叉树至多有2k-1个结点性质3对任何一棵二叉树T，如果其叶子结点数为n0,度为2的结点数为n2，则n0=n2+1第57页，课件共79页，创作于2023年2月123456789101112131415abcdefghij两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。第58页，课件共79页，创作于2023年2月性质4具有n(n≥1)个结点的完全二叉树的深度为[log2n]+1(其中[log2n]表示取log2n的整数部分)性质5如果对一棵有n个结点的完全二叉树的结点按顺序编号，则对任一结点i(1≤i≤n),有：（1）如果i=1,则结点i是二叉树的根，无双亲；如果i>1，则其双亲是[i/2]（2）如果2i＞n，则结点i无左孩子；否则其左孩子是结点2i（3）如果2i+1＞n，则结点i无右孩子；否则其右孩子是结点2i+1第59页，课件共79页，创作于2023年2月二叉树的存储结构完全二叉树顺序存储将完全二叉树中所有结点按编号顺序依次存储在一个地址连续的存储单元中。一般二叉树的顺序存储①将一般二叉树添上一些"虚结点"，成为"完全二叉树"②将各结点按编号顺序依次存储在一个地址连续的存储单元中，其中"虚结点"用""表示完全二叉树的顺序存储结构非完全二叉树的顺序存储结构第60页，课件共79页，创作于2023年2月二叉树的顺序存储结构的优缺点①对完全二叉树而言，顺序存储结构既简单又节省存储空间。②一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间,空间利用率仅为k/(2k-1)。③在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。第61页，课件共79页，创作于2023年2月二叉树链式存储结构用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。例：二叉树的二叉链表：

二叉链表结点的结构第62页，课件共79页，创作于2023年2月二叉树的遍历“遍历”是任何类型均有的操作。对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，存在多条遍历路径，所以就存在按什么样的搜索路径进行遍历的问题。第63页，课件共79页，创作于2023年2月二叉树的遍历顺着某一条搜索路径巡访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

遍历二叉树的过程实质是把二叉树的各结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。第64页，课件共79页，创作于2023年2月遍历方案

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。第65页，课件共79页，创作于2023年2月遍历二叉树的执行踪迹

三种递归遍历算法的搜索路线相同：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。

第66页，课件共79页，创作于2023年2月先根遍历算法：若二叉树为空树，则空操作；否则（1）访问根结点；（2）先根遍历左子树；（3）先根遍历右子树。先根遍历得到的先根序列为：

ABDCEF

第67页，课件共79页，创作于2023年2月中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中根遍历左子树；（2）访问根结点；（3）中根遍历右子树。中根序列为：

DBAECF

第68页，课件共79页，创作于2023年2月后（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后根遍历左子树；（2）后根遍历右子树；（3）访问根结点。后根序列为：

DBEFCA

第69页，课件共79页，创作于2023年2月先根遍历序列：

ABDFCE中根遍历序列：

BFDACE

后根遍历序列：

FDBECA例1：第70页，课件共79页，创作于2023年2月例2：先根遍历序列：

-+a*b-cd/ef中根遍历序列：

a+b*c-d-e/f

后根遍历序列：abcd-*+ef/-

第71页，课件共79页，创作于2023年2月ABCDEFGHK先根序列：中根序列：后根序列：A

BCD

EFGHKBDCA

EHGKFDCBHKGFE

A例3：第72页，课件共79页，创作于2023年2月先根遍历序列：

ABDHIECFGJ中根遍历序列

HDIBEAFCJG后根遍历序列：

HIDEBFJGCA例4：第73页，课件共79页，创作于2023年2月查找的定义查找的方法第74页，课件共79页，创作于2023年2月定义查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，若存在这样的数据元素说明查找是成功的，否则查找是不成功的。衡量查找算法好坏的标准是以平均查找比较的次数来定。查找方法顺序查找折半查找序号1234567891011数据513192137566475808892成功：采用顺序查找方法来查找21，需要比较4次；采用折半查找方法来查找21，需要比较3次；不成功：采用顺序查找方法来查找66，需要比较11次；采果采用折半查找方法来查找66，需要比较4次；第75页，课件共79页，创作于2023年2月选择排序交换排序插入排序第76页，课件共79页，创作于2023年2月排序是指将一个无序序列整理成一个按规定次序重新排列的有序序列。选择排序

原始序列8921564885161947第1遍选择1621564885891947第2遍选择1619564885892147第3遍选择1619214885895647第4遍选择1619214785895648第5遍选择1619