南邮数据结构作业答案省公共课一等奖全国赛课获奖课件.pptx

第一章第一章 习题讲解习题讲解1-19.确定以下各程序段程序步，确定划线语句执行次数，计确定以下各程序段程序步，确定划线语句执行次数，计算它们渐近时间复杂度。算它们渐近时间复杂度。(1)i=1;k=0;do k=k+10*i;i+;while(i=n-1)划线语句执行次数为划线语句执行次数为 n-1,渐近时间复杂度为渐近时间复杂度为O(n)(2）i=1;x=0;do x+;i=2*i;while（in）;划线语句执行次数为划线语句执行次数为 log2n ,渐近时间复杂度为渐近时间复杂度为O(log2n)10/10/1 1第1页(3)for(int i=1;i=n;i+)for(int j=1;j=i;j+)for(int k=1;k=(y+1)*(y+1)y+;划线语句执行次数为划线语句执行次数为 n1/2 ,渐近时间复杂度为渐近时间复杂度为O(n1/2)10/10/2 2第2页2-4Loc(Aijk)=134+(i*n*p+j*p+k)*2第二章第二章 习题讲解习题讲解10/10/3 3第3页2-9.设有长度为设有长度为n 一维整型数组一维整型数组A，设计一个算法，将原数组，设计一个算法，将原数组中元素以逆序排列中元素以逆序排列void Invert(T elements,int length)/length数组长度数组长度/elements为需要逆序数组为需要逆序数组 T e;for(int i=1;iLink;p-Link=first;first=p;p=q;return first;10/10/5 5第5页3-1.设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可马上出栈），问能否得到以下序列。若能得后可马上出栈），问能否得到以下序列。若能得到，则给出对应到，则给出对应push和和pop序列；若不能，则说序列；若不能，则说明理由。明理由。（1）A，B，C，D，E（1）能得到该序列。）能得到该序列。对应对应push和和pop序列为：序列为：push(A);pop();push(B);pop();push(C);pop();push(D);pop();push(E);pop();第三章第三章 习题讲解习题讲解10/10/6 6第6页3-1.设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可马上出栈），问能否得到以下序列。若能得后可马上出栈），问能否得到以下序列。若能得到，则给出对应到，则给出对应push和和pop序列；若不能，则说序列；若不能，则说明理由。明理由。（2）A，C，E，B，D（2）不能得到该序列，在）不能得到该序列，在E出栈时，出栈时，B和和D在栈在栈中，中，B比比D先进栈，所以先进栈，所以D应比应比B先出栈。先出栈。第三章第三章 习题讲解习题讲解10/10/7 7第7页（3）不能得到该序列，在）不能得到该序列，在C出栈时，出栈时，A和和B在栈中，在栈中，A比比B先进栈，所以先进栈，所以B应比应比A先出栈。先出栈。3-1.设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可马上出栈），问能否得到以下序列。若能得到，后可马上出栈），问能否得到以下序列。若能得到，则给出对应则给出对应push和和pop序列；若不能，则说明理序列；若不能，则说明理由。由。（3）C，A，B，D，E10/10/8 8第8页（4）能得到该序列。）能得到该序列。对应对应push和和pop序列为：序列为：push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();3-1.设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可马上出栈），问能否得到以下序列。若能得到，后可马上出栈），问能否得到以下序列。若能得到，则给出对应则给出对应push和和pop序列；若不能，则说明理序列；若不能，则说明理由。由。（4）E，D，C，B，A10/10/9 9第9页第四章第四章 习题讲解习题讲解4-1.设线性表采取次序表示方式，并假定次序表是设线性表采取次序表示方式，并假定次序表是有序（设有序（设表中元素已按非递减次序排列表中元素已按非递减次序排列）。编写函）。编写函数，实现线性表以下运算：数，实现线性表以下运算：（1）int Search_Insert(List*lst,T x)后置条件：在有序次序表中搜索元素后置条件：在有序次序表中搜索元素x。若若x在表中，则在表中，则返回返回x在表中位置在表中位置。不然，若表未满，则在表中插入新元素不然，若表未满，则在表中插入新元素x，而且插入，而且插入后，线性表依然是有序，后，线性表依然是有序，返回新元素返回新元素x位置位置；若表已满，无法插入新元素，则若表已满，无法插入新元素，则返回返回-1。10/10/1010第10页int Search_Insert(List*lst,T x)int i,j;for(i=0;(xlst-Elementsi)&(iSize);i+);/查找首个大于等于查找首个大于等于x元素位置，并统计在元素位置，并统计在i中中 if(lst-Elementsi=x)return i;/x在表中时，返回在表中时，返回x位置位置 if(IsFull(lst)/或或if(lst-Size=lst-maxList)return-1;/表已满时，无法插入，返回表已满时，无法插入，返回-1 for(j=lst-Size-1;j=i;j-)lst-Elementj+1=lst-Elementj;lst-Elementi=x;/新元素即插入位置新元素即插入位置i处处 lst.Size+;return i;/插入新元素并返回该元素位置插入新元素并返回该元素位置10/10/1111第11页4-1.设线性表采取次序表示方式，并假定次序表是设线性表采取次序表示方式，并假定次序表是有序（设有序（设表中元素已按非递减次序排列表中元素已按非递减次序排列）。编写函）。编写函数，实现线性表以下运算：数，实现线性表以下运算：（2）void Search_Delete(List*lst,T x,T y)前置条件：前置条件：xSize=0)printf(“The list is empty”);return-1;int i,j,sum=0;for(i=0;tempix&in-1)return;/没有符合条件元素没有符合条件元素 for(j=i;lstj=y&jn;j+);/找到首个大于找到首个大于y元素位置元素位置j sum=j-i;while(jn)lsti+=lstj+;/删除删除sum个元素个元素 n=n-sum;for(j=i;jy)/大于大于y元素前移元素前移lsti+=lstj+;else/小于等于小于等于y元素删除元素删除 j+;n-;10/10/1313第13页4.6 4.6 给出以下稀疏矩阵行优先和列优先次序存放行给出以下稀疏矩阵行优先和列优先次序存放行给出以下稀疏矩阵行优先和列优先次序存放行给出以下稀疏矩阵行优先和列优先次序存放行三元组和列三元组表示。三元组和列三元组表示。三元组和列三元组表示。三元组和列三元组表示。列三元组：列三元组：4.7 求对题图求对题图4-1稀疏矩阵执行矩阵转置时数组稀疏矩阵执行矩阵转置时数组num和和k值。值。col01234numcol10212kcol01134行三元组行三元组：10/10/1414第14页6-2.6-2.对于三个结点对于三个结点对于三个结点对于三个结点A A，B B和和和和C C，可分别组成多少不一，可分别组成多少不一，可分别组成多少不一，可分别组成多少不一样无序树、有序树和二叉树？样无序树、有序树和二叉树？样无序树、有序树和二叉树？样无序树、有序树和二叉树？（1）无序树：）无序树：9棵棵（2）有序树：）有序树：12棵棵（3）二叉树：）二叉树：30棵棵3棵棵6棵棵6棵棵6棵棵各各6棵棵第六章第六章 习题讲解习题讲解10/10/1515第15页6-3.设在度为设在度为m树中，度为树中，度为1，2，m节点个数节点个数分别为分别为n1,n2,nm，求叶子节点数目。，求叶子节点数目。设度为设度为0节点个数为节点个数为n0则：则：树总度数树总度数=节点总个数节点总个数-1即：即：1*n1+2*n2+m*nm=n0+n1+n2+n3+.+nm-1所以叶子节点数目为：所以叶子节点数目为：n0=n2+2*n3+.+(m-1)nm+110/10/1616第16页6-5.找出全部二叉树，其节点在以下两种次序下找出全部二叉树，其节点在以下两种次序下恰好都以一样次序出现：恰好都以一样次序出现：（1）先序和中序；（）先序和中序；（2）先序和后序；（）先序和后序；（3）中）中序和后序序和后序（1）或者为空二叉树，或者全部结点左子树都是）或者为空二叉树，或者全部结点左子树都是空单支树空单支树（2）或者为空二叉树，或者只有根结点二叉树）或者为空二叉树，或者只有根结点二叉树（3）或者为空二叉树，或者全部结点右子树都是）或者为空二叉树，或者全部结点右子树都是空单支树空单支树10/10/1717第17页6-6.6-6.设对一棵二叉树进行中序遍历和后序遍历结果分设对一棵二叉树进行中序遍历和后序遍历结果分设对一棵二叉树进行中序遍历和后序遍历结果分设对一棵二叉树进行中序遍历和后序遍历结果分别为：别为：别为：别为：（1 1）中序遍历）中序遍历）中序遍历）中序遍历 （B D C EB D C E）A A （F H G F H G）（2 2）后序遍历）后序遍历）后序遍历）后序遍历 （D E C BD E C B）（）（）（）（H G FH G F）A A 画出该二叉树。画出该二叉树。画出该二叉树。画出该二叉树。ABFCDEGH10/10/1818第18页6-7 6-7 写出下列图中二叉树先序、中序和后序遍历结果写出下列图中二叉树先序、中序和后序遍历结果写出下列图中二叉树先序、中序和后序遍历结果写出下列图中二叉树先序、中序和后序遍历结果先序：先序：DEHFJGCKAB中序：中序：HEJFGKCDAB后序：后序：HJKCGFEBADDEAFJGBCHK10/10/1919第19页int SizeL(BTree Bt)return SizeofLeaf(Bt.Root);int SizeofLeaf(BTNode*p)if(!p)return 0;if(!(p-RChild)&(!(p-LChild)return 1;return SizeofLeaf(p-LChild)+SizeofLeaf(p-RChild);6-8.6-8.设二叉树以二叉链表存放，试编写求解以下问设二叉树以二叉链表存放，试编写求解以下问设二叉树以二叉链表存放，试编写求解以下问设二叉树以二叉链表存放，试编写求解以下问题递归算法：题递归算法：题递归算法：题递归算法：（3 3）求一棵二叉树中叶结点个数；）求一棵二叉树中叶结点个数；）求一棵二叉树中叶结点个数；）求一棵二叉树中叶结点个数；10/10/2020第20页（4 4）设计算法，交换一棵二叉树中每个结点左、设计算法，交换一棵二叉树中每个结点左、设计算法，交换一棵二叉树中每个结点左、设计算法，交换一棵二叉树中每个结点左、右子树。右子树。右子树。右子树。void ExchBt(BTree Bt)Exch(Bt.Root);void Exch(BTNode*p)if(p)BTNode*q=p-LChild;p-LChild=p-RChild;p-RChild=q;Exch(p-LChild);Exch(p-RChild);10/10/2121第21页6-13.6-13.将上图中树转换成二叉树，并将下列图中二叉将上图中树转换成二叉树，并将下列图中二叉将上图中树转换成二叉树，并将下列图中二叉将上图中树转换成二叉树，并将下列图中二叉树转换成森林。树转换成森林。树转换成森林。树转换成森林。10/10/2222第22页6-18.6-18.设设设设S=A,B,C,D,E,FS=A,B,C,D,E,F，W=2,3,5,7,9,12W=2,3,5,7,9,12，对字符集合进行哈夫曼编码，对字符集合进行哈夫曼编码，对字符集合进行哈夫曼编码，对字符集合进行哈夫曼编码，WW为各字符频率为各字符频率为各字符频率为各字符频率（1 1）画出哈夫曼树）画出哈夫曼树）画出哈夫曼树）画出哈夫曼树（2 2）计算带权路径长度）计算带权路径长度）计算带权路径长度）计算带权路径长度（3 3）求各字符编码）求各字符编码）求各字符编码）求各字符编码 A:1010 B:1011 C:100 D:00 E:01 F:11加权路径长度：加权路径长度：WPL=(2+3)4+53+(7+9+12)2=91 10/10/2323第23页7-47-47-47-4为何说对半搜索算法只适合用于次序有序表情为何说对半搜索算法只适合用于次序有序表情为何说对半搜索算法只适合用于次序有序表情为何说对半搜索算法只适合用于次序有序表情况？为何说次序搜索可用于次序表和链表，也不况？为何说次序搜索可用于次序表和链表，也不况？为何说次序搜索可用于次序表和链表，也不况？为何说次序搜索可用于次序表和链表，也不受表有序性限制？受表有序性限制？受表有序性限制？受表有序性限制？解：解：解：解：1 1、对半搜索对半搜索对半搜索对半搜索算法必须针对次序存放有序表，要求算法必须针对次序存放有序表，要求算法必须针对次序存放有序表，要求算法必须针对次序存放有序表，要求满足两个条件：满足两个条件：满足两个条件：满足两个条件：1 1）次序存放，只有次序存放才能够依据元素下）次序存放，只有次序存放才能够依据元素下）次序存放，只有次序存放才能够依据元素下）次序存放，只有次序存放才能够依据元素下标（地址）随机存取元素；标（地址）随机存取元素；标（地址）随机存取元素；标（地址）随机存取元素；2 2）有序存放，只有有序存放才能够其实现对半）有序存放，只有有序存放才能够其实现对半）有序存放，只有有序存放才能够其实现对半）有序存放，只有有序存放才能够其实现对半查找。查找。查找。查找。2 2、次序搜索次序搜索次序搜索次序搜索从头到尾逐一查找，所以可用于次序从头到尾逐一查找，所以可用于次序从头到尾逐一查找，所以可用于次序从头到尾逐一查找，所以可用于次序表和链表，也不受表有序性限制。表和链表，也不受表有序性限制。表和链表，也不受表有序性限制。表和链表，也不受表有序性限制。10/10/2424第24页补充：已知（补充：已知（补充：已知（补充：已知（1 1 1 1，2 2 2 2，3 3 3 3，4 4 4 4，5 5 5 5，6 6 6 6，7 7 7 7，8 8 8 8，9 9 9 9，10101010，11111111）找到）找到）找到）找到9 9 9 9比较几次？比较几次？比较几次？比较几次？解：解：解：解：第一次比较：第一次比较：第一次比较：第一次比较：M=(1+11)/2=6M=(1+11)/2=6，6969，找找找找77，1111；第第第第2 2次比较：次比较：次比较：次比较：M=(7+11)/2=9M=(7+11)/2=9，9=9 9=9，成功。成功。成功。成功。所以一共比较所以一共比较所以一共比较所以一共比较2 2次成功次成功次成功次成功10/10/2525第25页8-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，25252525，14141414，76767676，56565656，65656565为输入为输入为输入为输入时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除76767676，45454545，则树，则树，则树，则树形分别怎样？形分别怎样？形分别怎样？形分别怎样？3725451456659176建成二叉树建成二叉树10/10/2626第26页8-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，25252525，14141414，76767676，56565656，65656565为输入为输入为输入为输入时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除76767676，45454545，则树，则树，则树，则树形分别怎样？形分别怎样？形分别怎样？形分别怎样？37254514566591删除删除76后后10/10/2727第27页8-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，25252525，14141414，76767676，56565656，65656565为输入为输入为输入为输入时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除时二叉搜索树，再从该树上依次删除76767676，45454545，则树，则树，则树，则树形分别怎样？形分别怎样？形分别怎样？形分别怎样？372514566591删除删除45后后10/10/2828第28页8-3 8-3 8-3 8-3 已知对一棵二叉搜索树进行先序遍历结果是：已知对一棵二叉搜索树进行先序遍历结果是：已知对一棵二叉搜索树进行先序遍历结果是：已知对一棵二叉搜索树进行先序遍历结果是：28282828，25252525，36363636，33333333，35353535，34343434，43434343，请画出此二叉搜，请画出此二叉搜，请画出此二叉搜，请画出此二叉搜索树。索树。索树。索树。2825363435433310/10/2929第29页9-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key%11h(key)=key%11。采取线性探查法、二次探查法处理冲突，试用关键采取线性探查法、二次探查法处理冲突，试用关键字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，5555分别分别建立散列表。建立散列表。线性探查法：线性探查法：Keyh(Key)704253803352605451506550055453525708060501234567891010/10/3030第30页9-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key%11h(key)=key%11。采取线性探查法、二次探查法处理冲突，试用关键采取线性探查法、二次探查法处理冲突，试用关键字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，5555分别分别建立散列表。建立散列表。二次探查法：二次探查法：Keyh(Key)704253803352605451506550045358025706050551234567891010/10/3131第31页9-4 9-4 对上题例子，若采取双散列法，试以散列函数对上题例子，若采取双散列法，试以散列函数h h1 1(key)=key%11(key)=key%11，h h2 2(key)=key%9+1(key)=key%9+1建立散列表。建立散列表。0558035257060455012345678910Keyh1(Key)704253803352605451506550h2(Key)88997162对80：（3+1*9）%11=1 对45：（1+1*1）%11=2（1+2*1）%11=3（1+3*1）%11=4 （1+4*1）%11=5（1+5*1）%11=6 对50：（6+1*6）%11=1 （6+2*6）%11=710/10/3232第32页10-1 10-1 对如图所表示有向图，求：对如图所表示有向图，求：对如图所表示有向图，求：对如图所表示有向图，求：(1)(1)每个顶点入度和出度；每个顶点入度和出度；每个顶点入度和出度；每个顶点入度和出度；(2)(2)强连通分量；强连通分量；强连通分量；强连通分量；(3)(3)邻接矩阵。邻接矩阵。邻接矩阵。邻接矩阵。5 52 24 41 13 30 0(1)(1)各个顶点入度和出度各个顶点入度和出度顶点顶点 入度入度 出度出度0 03 30 01 12 22 22 21 12 23 31 12 24 42 23 35 51 11 1(2)(2)强连通分量强连通分量(3)(3)邻接矩阵邻接矩阵0 00 00 00 00 00 01 01 00 10 10 00 00 10 10 00 01 01 00 00 01 01 01 01 01 11 10 00 00 10 11 01 00 00 00 00 02 24 41 13 35 50 010/10/3333第33页10-2 10-2 从只有从只有从只有从只有6 6个顶点没有边图开始，以边个顶点没有边图开始，以边个顶点没有边图开始，以边个顶点没有边图开始，以边,次序，经过使用程序次序，经过使用程序次序，经过使用程序次序，经过使用程序10-4Add10-4Add函数插入函数插入函数插入函数插入这些边，建立该图邻接表结构。请画出所建成邻接表这些边，建立该图邻接表结构。请画出所建成邻接表这些边，建立该图邻接表结构。请画出所建成邻接表这些边，建立该图邻接表结构。请画出所建成邻接表结构。结构。结构。结构。5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 510/10/3434第34页10-4 10-4 已知有向图邻接表，写出计算各个顶点入度算已知有向图邻接表，写出计算各个顶点入度算已知有向图邻接表，写出计算各个顶点入度算已知有向图邻接表，写出计算各个顶点入度算法。法。法。法。void Degree(Graph g,int*d)int i;int n=g.Vertices;Enode*p;for(i=0;in;i+)di=0;for(i=0;inextArc)dp-adjVex+;for(i=0;in;i+)cout“d“i“=“di;10/10/3535第35页10-6 10-6 在题在题10-210-2所建立邻接表上进行以顶点所建立邻接表上进行以顶点2 2为起点为起点顶点深度优先搜索和宽度优先搜索。分别画出遍历顶点深度优先搜索和宽度优先搜索。分别画出遍历所得到深度优先搜索和宽度优先搜索生成森林（或所得到深度优先搜索和宽度优先搜索生成森林（或生成树）。生成树）。5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5题题10-2所建立邻接所建立邻接表对应图为：表对应图为：10/10/3636第36页以顶点以顶点2为起点顶点深度优先搜为起点顶点深度优先搜索所得到深度优先搜索生成树：索所得到深度优先搜索生成树：0 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 55 52 24 41 13 30 0深度优先遍历：深度优先遍历：2，4，5，0，1，310/10/3737第37页以顶点以顶点2为起点顶点宽度优先搜为起点顶点宽度优先搜索所得到宽度优先搜索生成树：索所得到宽度优先搜索生成树：5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5宽度优先遍历：宽度优先遍历：2，4，1，5，0，310/10/3838第38页10-14 10-14 10-14 10-14 使用普里姆算法以使用普里姆算法以使用普里姆算法以使用普里姆算法以1 1 1 1为源点，画出图为源点，画出图为源点，画出图为源点，画出图10-2710-2710-2710-27无无无无向图最小代价生成树。向图最小代价生成树。向图最小代价生成树。向图最小代价生成树。4 42 25 50 03 31 11 17 72 21 15 56 69 92 24 42 25 50 03 31 11 17 72 21 15 5Prim算法以算法以1为源点，生成最小代价生成树为：为源点，生成最小代价生成树为：10/10/3939第39页11-2 11-2 设有统计序列：设有统计序列：设有统计序列：设有统计序列：6161，8787，1212，0303，0808，7070，9797，7575，5353，2626。现按以下算法对它分别进行排。现按以下算法对它分别进行排。现按以下算法对它分别进行排。现按以下算法对它分别进行排序，请手工模拟算法执行过程，给出每趟排序结果。序，请手工模拟算法执行过程，给出每趟排序结果。序，请手工模拟算法执行过程，给出每趟排序结果。序，请手工模拟算法执行过程，给出每趟排序结果。（1 1）直接插入排序）直接插入排序）直接插入排序）直接插入排序（3 3）冒泡排序）冒泡排序）冒泡排序）冒泡排序（4 4）快速排序）快速排序）快速排序）快速排序（5 5）简单项选择择排序）简单项选择择排序）简单项选择择排序）简单项选择择排序10/10/4040第40页（1）直接插入排序）直接插入排序初始序列（初始序列（61）87 12 03 08 70 97 75 53 26第第1趟趟（61 87）12 03 08 70 97 75 53 26第第2趟趟（12 61 87）03 08 70 97 75 53 26第第3趟趟（03 12 61 87）08 70 97 75 53 26第第4趟趟（03 08 12 61 87）70 97 75 53 26第第5趟趟（03 08 12 61 70 87）97 75 53 26第第6趟趟（03 08 12 61 70 87 97）75 53 26第第7趟趟（03 08 12 61 70 75 87 97）53 26第第8趟趟（03 08 12 53 61 70 75 87 97）26第第9趟趟（03 08 12 26 53 61 70 75 87 97）10/10/4141第41页（3）冒泡排序（注意冒泡排序只排了）冒泡排序（注意冒泡排序只排了7趟）趟）初始序列初始序列(61 87 12 03 08 70 97 75 53 26)第第1趟趟 61 12 03 08 70 87 75 53 26 97 第第2趟趟 12 03 08 61 70 75 53 26 87 97第第3趟趟 03 08 12 61 70 53 26 75 87 97第第4趟趟 03 08 12 61 53 26 70 75 87 97第第5趟趟 03 08 12 53 26 61 70 75 87 97第第6趟趟 03 08 12 26 53 61 70 75 87 97第第7趟趟 03 08 12 26 53 61 70 75 87 9710/10/4242第42页（4）快速排序）快速排序初始序列初始序列61 87 12 03 08 70 97 75 53 26 第第1趟趟 (53 26 12 3 8)61 (97 75 70 87)第第2趟趟 (8 26 12 3)53 61 (97 75 70 87)第第3趟趟 (3)8 (12 26)53 61 (97 75 70 87)第第4趟趟 3 8 12 (26)53 61 (97 75 70 87)第第5趟趟 3 8 12 26 53 61 (87 75 70)97 第第6趟趟 3 8 12 26 53 61 (70 75)87 97 第第7趟趟 3 8 12 26 53 61 70 (75)87 97 10/10/4343第43页（5）简单项选择择排序）简单项选择择排序初始序列初始序列 61 87 12 03 08 70 97 75 53 26第第1趟趟 （03）87 12 61 08 70 97 75 53 26第第2趟趟 （03 08）12 61 87 70 97 75 53 26第第3趟趟 （03 08 12）61 87 70 97 75 53 26第第4趟趟 （03 08 12 26）87 70 97 75 53 61第第5趟趟 （03 08 12 26 53）70 97 75 87 61第第6趟趟 （03 08 12 26 53 61）97 75 87 70第第7趟趟 （03 08 12 26 53 61 70）75 87 97第第8趟趟 （03 08 12 26 53 61 70 75）87 97第第9趟趟 （03 08 12 26 53 61 70 75 87）9710/10/4444第44页11-4 11-4 从以下几个方面比较题从以下几个方面比较题从以下几个方面比较题从以下几个方面比较题11-211-2中各种排序算法。中各种排序算法。中各种排序算法。中各种排序算法。（1 1）最好、最坏和平均情况下时间复杂度；）最好、最坏和平均情况下时间复杂度；）最好、最坏和平均情况下时间复杂度；）最好、最坏和平均情况下时间复杂度；（3 3）稳定性（对不稳定算法给出一个简单实例）；）稳定性（对不稳定算法给出一个简单实例）；）稳定性（对不稳定算法给出一个简单实例）；）稳定性（对不稳定算法给出一个简单实例）；（4 4）指出第）指出第）指出第）指出第1 1趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终位置算法。位置算法。位置算法。位置算法。10/10/4545第45页（1）最好、最坏和平均情况下时间复杂度：）最好、最坏和平均情况下时间复杂度：简单项选择择排序简单项选择择排序:三种情况下时间复杂度都为三种情况下时间复杂度都为O(n2)。直接插入排序：直接插入排序：最好情况下为最好情况下为O(n)；平均和最坏情况下为平均和最坏情况下为O(n2)。冒泡排序：冒泡排序：最好情况为最好情况为O(n)；最坏和平均情况下为最坏和平均情况下为O(n2)。快速排序：快速排序：最好和平均情况下为最好和平均情况下为O(nlog2n)；最坏情况下时间复杂度为最坏情况下时间复杂度为O(n2)。10/10/4646第46页（3）稳定性：）稳定性：不稳定是简单项选择择排序和快速排序两种，其它不稳定是简单项选择择排序和快速排序两种，其它是稳定。是稳定。实例：实例：3 3 1 简单项选择择排序过后变成了简单项选择择排序过后变成了 1 3 3，3 4 3 快速排序之后变成了快速排序之后变成了3 3 4 10/10/4747第47页（4）第一趟排序结束后就能确定某个元素最终位）第一趟排序结束后就能确定某个元素最终位置算法：置算法：简单项选择择排序：确定最小元素在第一位简单项选择择排序：确定最小元素在第一位冒泡排序：确定最大元素在最终一位冒泡排序：确定最大元素在最终一位快速排序：确立分割元素在中间快速排序：确立分割元素在中间10/10/4848第48页最好最好最坏最坏平均平均最最终终位置位置稳稳定性定性简单项选择择排序O(n2)O(n2)O(n2)能能不不稳稳定定直接插入直接插入排序排序O(n)O(n2)O(n2)不能不能稳稳定定冒泡排序冒泡排序O(n)O(n2)O(n2)能能稳稳定定快速排序快速排序O(nlog2n)O(n2)O(nlog2n)能能不不稳稳定定10/10/4949第49页