《南邮数据结构作业答案讲解文档资料》由会员分享，可在线阅读，更多相关《南邮数据结构作业答案讲解文档资料（49页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 习题讲解习题讲解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)7/29/20247/29/20241 1(3)
2、 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)7/29/20247/29/20242 22-4Loc(Aijk)=134+(i*n*p+j*p+k)*2第二章第二章 习题讲解习题讲解7/29/20247/29/20243 32-9. 设有长度为设有长度为n 的一维整型数组的一维整型数组A，设计一个算法，将原数，设计一个算法，将原数组中的元素以逆序排列组中的元素以逆序排列void Invert(T el
3、ements, int length) /length数组长度数组长度/elements为需要逆序的数组为需要逆序的数组 T e; for (int i=1;iLink; p-Link=first;first=p; p=q;return first; 7/29/20247/29/20245 53-1. 设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得后可立即出栈），问能否得到下列序列。若能得到，则给出相应的到，则给出相应的push和和pop序列；若不能，则序列；若不能，则说明理由。说明理由。（1）A，B，C，D，E（1）能得到该序列。
4、）能得到该序列。相应的相应的push和和pop序列为：序列为：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(E); pop(); 第三章第三章 习题讲解习题讲解7/29/20247/29/20246 63-1. 设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得后可立即出栈），问能否得到下列序列。若能得到，则给出相应的到，则给出相应的push和和pop序列；若不能，则序列；若不能，则说明理由。说明理由。（2）A，C，E，B，D（2）不能得到该序列
5、，在）不能得到该序列，在E出栈时，出栈时，B和和D在栈在栈中，中，B比比D先进栈，所以先进栈，所以D应比应比B先出栈。先出栈。第三章第三章 习题讲解习题讲解7/29/20247/29/20247 7（3）不能得到该序列，在）不能得到该序列，在C出栈时，出栈时，A和和B在栈中，在栈中，A比比B先进栈，所以先进栈，所以B应比应比A先出栈。先出栈。 3-1. 设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，后可立即出栈），问能否得到下列序列。若能得到，则给出相应的则给出相应的push和和pop序列；若不能，则说明序列；若不能，则说明理由
6、。理由。（3）C，A，B，D，E7/29/20247/29/20248 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，A
7、7/29/20247/29/20249 9第四章第四章 习题讲解习题讲解4-1. 设线性表采用顺序表示方式，并假定顺序表是有设线性表采用顺序表示方式，并假定顺序表是有序的（设序的（设表中元素已按非递减次序排列表中元素已按非递减次序排列）。编写函数）。编写函数，实现线性表的如下运算：，实现线性表的如下运算：（1）int Search_Insert(List *lst,T x)后置条件：在有序的顺序表中搜索元素后置条件：在有序的顺序表中搜索元素x。若若x在表中，则在表中，则返回返回x在表中的位置在表中的位置。否则，若表未满，则在表中插入新元素否则，若表未满，则在表中插入新元素x，并且插入，并且插入
8、后，线性表仍然是有序的，后，线性表仍然是有序的，返回新元素返回新元素x的位置的位置；若表已满，无法插入新元素，则若表已满，无法插入新元素，则返回返回-1。7/29/20247/29/20241010int 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(l
9、st-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;/插入新元素并返回该元素的位置插入新元素并返回该元素的位置7/29/20247/29/202411114-1. 设线性表采用顺序表示方式，并假定顺序表是有设线性表采用顺序表示方式，并假定顺序表是有序的（设序的（设表中元素已按非递减次序排列表中元素已按非递减
10、次序排列）。编写函数）。编写函数，实现线性表的如下运算：，实现线性表的如下运算：（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=
11、n-sum;for (j=i;jy) /大于大于y的元素前移的元素前移lsti+=lstj+;else/小于等于小于等于y的元素删除的元素删除 j+; n-; 7/29/20247/29/202413134.6 4.6 给出下列稀疏矩阵的行优先和列优先顺序存储给出下列稀疏矩阵的行优先和列优先顺序存储给出下列稀疏矩阵的行优先和列优先顺序存储给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。的行三元组和列三元组表示。的行三元组和列三元组表示。的行三元组和列三元组表示。列三元组：列三元组： 4.7 求对题图求对题图4-1的稀疏矩阵执行矩阵转置时数组的稀疏矩阵执行矩阵转置时数组num和
12、和k的值。的值。col01234numcol10212kcol01134行三元组行三元组： 7/29/20247/29/202414146-2. 6-2. 对于三个结点对于三个结点对于三个结点对于三个结点A A，B B和和和和C C，可分别组成多少不同，可分别组成多少不同，可分别组成多少不同，可分别组成多少不同的无序树、有序树和二叉树？的无序树、有序树和二叉树？的无序树、有序树和二叉树？的无序树、有序树和二叉树？（1）无序树：）无序树：9棵棵（2）有序树：）有序树：12棵棵（3）二叉树：）二叉树：30棵棵3棵棵6棵棵6棵棵6棵棵各各6棵棵第六章第六章 习题讲解习题讲解7/29/20247/29
13、/202415156-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+17/29/20247/29/202416166-5. 找出所有二叉树，其节点在下列两种次序下找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现：恰好都以同样的次
14、序出现：（1）先序和中序；（）先序和中序；（2）先序和后序；（）先序和后序；（3）中）中序和后序序和后序（1）或者为空二叉树，或者所有结点的左子树都）或者为空二叉树，或者所有结点的左子树都是空的单支树是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所有结点的右子树都）或者为空二叉树，或者所有结点的右子树都是空的单支树是空的单支树7/29/20247/29/202417176-6. 6-6. 设对一棵二叉树进行中序遍历和后序遍历的结果设对一棵二叉树进行中序遍历和后序遍历的结果设对一棵二叉树进行中序遍历和后序遍历的结果设对一
15、棵二叉树进行中序遍历和后序遍历的结果分别为：分别为：分别为：分别为： （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 画出该二叉树。画出该二叉树。画出该二叉树。画出该二叉树。ABFCDEGH7/29/20247/29/202418186-7 6-7 写出下图中二叉树的先序、中序和后序遍历结果写出下图中二叉树的先序、中序和后序遍历结果写出下图中二叉树的先序、中序和后序遍历结果写出下图中二叉树的先序
16、、中序和后序遍历结果先序：先序：DEHFJGCKAB中序：中序：HEJFGKCDAB后序：后序：HJKCGFEBADDEAFJGBCHK7/29/20247/29/20241919int 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.设二叉树以二叉链表存储，试编写求解下列问
17、设二叉树以二叉链表存储，试编写求解下列问设二叉树以二叉链表存储，试编写求解下列问设二叉树以二叉链表存储，试编写求解下列问题的递归算法：题的递归算法：题的递归算法：题的递归算法：（3 3）求一棵二叉树中的叶结点个数；）求一棵二叉树中的叶结点个数；）求一棵二叉树中的叶结点个数；）求一棵二叉树中的叶结点个数；7/29/20247/29/20242020（4 4）设计算法，交换一棵二叉树中每个结点的左、设计算法，交换一棵二叉树中每个结点的左、设计算法，交换一棵二叉树中每个结点的左、设计算法，交换一棵二叉树中每个结点的左、右子树。右子树。右子树。右子树。void ExchBt(BTree Bt)Exch
18、(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);7/29/20247/29/202421216-13. 6-13. 将上图中的树转换成二叉树，并将下图中的二将上图中的树转换成二叉树，并将下图中的二将上图中的树转换成二叉树，并将下图中的二将上图中的树转换成二叉树，并将下图中的二叉树转换成森林。叉树转换成森林。叉树转换成森林。叉树转换成森林。7/29/20247/29/202422226-18. 6-18. 设设设设S
19、=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
20、+3)4+53+(7+9+12)2=91 7/29/20247/29/202423237-47-47-47-4为什么说对半搜索算法只适用于顺序有序表的为什么说对半搜索算法只适用于顺序有序表的为什么说对半搜索算法只适用于顺序有序表的为什么说对半搜索算法只适用于顺序有序表的情况？为什么说顺序搜索可用于顺序表和链表，情况？为什么说顺序搜索可用于顺序表和链表，情况？为什么说顺序搜索可用于顺序表和链表，情况？为什么说顺序搜索可用于顺序表和链表，也不受表的有序性限制？也不受表的有序性限制？也不受表的有序性限制？也不受表的有序性限制？解：解：解：解：1 1、对半搜索对半搜索对半搜索对半搜索算法必须针对顺序存
21、储的有序表，要算法必须针对顺序存储的有序表，要算法必须针对顺序存储的有序表，要算法必须针对顺序存储的有序表，要求满足两个条件：求满足两个条件：求满足两个条件：求满足两个条件： 1 1）顺序存储，只有顺序存储才可以根据元素下）顺序存储，只有顺序存储才可以根据元素下）顺序存储，只有顺序存储才可以根据元素下）顺序存储，只有顺序存储才可以根据元素下标（地址）随机存取元素；标（地址）随机存取元素；标（地址）随机存取元素；标（地址）随机存取元素； 2 2）有序存储，只有有序存储才可以其实现对半）有序存储，只有有序存储才可以其实现对半）有序存储，只有有序存储才可以其实现对半）有序存储，只有有序存储才可以其实
22、现对半查找。查找。查找。查找。2 2、顺序搜索顺序搜索顺序搜索顺序搜索从头到尾逐个查找，所以可用于顺序从头到尾逐个查找，所以可用于顺序从头到尾逐个查找，所以可用于顺序从头到尾逐个查找，所以可用于顺序表和链表，也不受表的有序性限制。表和链表，也不受表的有序性限制。表和链表，也不受表的有序性限制。表和链表，也不受表的有序性限制。7/29/20247/29/20242424补充：已知（补充：已知（补充：已知（补充：已知（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）找
23、到）找到）找到）找到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次成功次成功次成功次成功7/29/20247/29/202425258-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，252525
24、25，14141414，76767676，56565656，65656565为输入为输入为输入为输入时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除76767676，45454545，则，则，则，则树形分别如何？树形分别如何？树形分别如何？树形分别如何？ 3725451456659176建成的二叉树建成的二叉树7/29/20247/29/202426268-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，25252525，14141414，76767676，
25、56565656，65656565为输入为输入为输入为输入时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除76767676，45454545，则，则，则，则树形分别如何？树形分别如何？树形分别如何？树形分别如何？ 37254514566591删除删除76后后7/29/20247/29/202427278-1 8-1 8-1 8-1 建立建立建立建立37373737，45454545，91919191，25252525，14141414，76767676，56565656，65656565为输入为输入为输入为
26、输入时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除时的二叉搜索树，再从该树上依次删除76767676，45454545，则，则，则，则树形分别如何？树形分别如何？树形分别如何？树形分别如何？ 372514566591删除删除45后后7/29/20247/29/202428288-3 8-3 8-3 8-3 已知对一棵二叉搜索树进行先序遍历的结果已知对一棵二叉搜索树进行先序遍历的结果已知对一棵二叉搜索树进行先序遍历的结果已知对一棵二叉搜索树进行先序遍历的结果是：是：是：是：28282828，25252525，36363636，3333333
27、3，35353535，34343434，43434343，请画出此二，请画出此二，请画出此二，请画出此二叉搜索树。叉搜索树。叉搜索树。叉搜索树。 282536343543337/29/20247/29/202429299-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key % 11h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键字采用线性探查法、二次探查法解决冲突，试用关键字值序列：值序列：7070，2525，8080，3535，6060，4545，5050，5555分别建立分别建立散列表。散列表。线性探查法：线性探查法：Keyh(
28、Key)70425380335260545150655005545352570806050123456789107/29/20247/29/202430309-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key % 11h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键采用线性探查法、二次探查法解决冲突，试用关键字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，5555分别分别建立散列表。建立散列表。二次探查法：二次探查法：Keyh(Key)704253803352605451506550045
29、35802570605055123456789107/29/20247/29/202431319-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）%
30、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=77/29/20247/29/2024323210-1 10-1 对如图所示的有向图，求：对如图所示的有向图，求：对如图所示的有向图，求：对如图所示的有向图，求：(1)(1)每个顶点的入度和出度；每个顶点的入度和出度；每个顶点的入度和出度；每个顶点的入度和出度；(2)(2)强连通分量；强连通分量；强连通分量；强连通分量；(3)(3)邻接矩阵。邻接矩阵。邻接矩阵。邻接矩阵。5 52 24 41 13 30 0(1)(1)各个顶点的入度和出度各个顶点的入度和出
31、度顶点顶点 入度入度 出度出度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 07/29/20247/29/2024333310-2 10-2 从只有从只有从只有从只有6 6个顶点没有边的图开始，以边个顶点没有边的图开始，以边个顶
32、点没有边的图开始，以边个顶点没有边的图开始，以边, , , , , , , , , , , , , , , , , , 的次序，通过使用程序的次序，通过使用程序的次序，通过使用程序的次序，通过使用程序10-410-4的的的的AddAdd函数函数函数函数插入这些边，建立该图的邻接表结构。请画出所建成插入这些边，建立该图的邻接表结构。请画出所建成插入这些边，建立该图的邻接表结构。请画出所建成插入这些边，建立该图的邻接表结构。请画出所建成的邻接表结构。的邻接表结构。的邻接表结构。的邻接表结构。5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4
33、 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 57/29/20247/29/2024343410-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;
34、i+) cout“d“i“=“di;7/29/20247/29/2024353510-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-
35、2所建立的邻所建立的邻接表对应的图为：接表对应的图为：7/29/20247/29/20243636以顶点以顶点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，37/29/20247/29/20243737以顶点以顶点2为起点顶点的宽度优先为起点顶点的宽度优先搜索所得到宽度优先搜索生成树：搜索所得到宽度优先搜索
36、生成树：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，37/29/20247/29/2024383810-14 10-14 10-14 10-14 使用普里姆算法以使用普里姆算法以使用普里姆算法以使用普里姆算法以1 1 1 1为源点，画出图为源点，画出图为源点，画出图为源点，画出图10-2710-2710-2710-27的的的的无向图的最小代价生成树。无向图的最小代价生成树。无向图的最小代价生成树。无向图的
37、最小代价生成树。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为源点，生成的最小代价生成树为：为源点，生成的最小代价生成树为：7/29/20247/29/2024393911-2 11-2 设有记录序列：设有记录序列：设有记录序列：设有记录序列：6161，8787，1212，0303，0808，7070，9797，7575，5353，2626。现按下列算法对它分别进行排。现按下列算法对它分别进行排。现按下列算法对它分别进行排。现按下列算法对它分别进行排序，请手工模拟算法
38、的执行过程，给出每趟排序结序，请手工模拟算法的执行过程，给出每趟排序结序，请手工模拟算法的执行过程，给出每趟排序结序，请手工模拟算法的执行过程，给出每趟排序结果。果。果。果。（1 1）直接插入排序）直接插入排序）直接插入排序）直接插入排序（3 3）冒泡排序）冒泡排序）冒泡排序）冒泡排序（4 4）快速排序）快速排序）快速排序）快速排序（5 5）简单选择排序）简单选择排序）简单选择排序）简单选择排序7/29/20247/29/20244040（1）直接插入排序）直接插入排序初始序列（初始序列（61）87 12 03 08 70 97 75 53 26第第1趟趟 （61 87）12 03 08 70
39、 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
40、） 7/29/20247/29/20244141（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
41、70 75 87 97第第7趟趟 03 08 12 26 53 61 70 75 87 977/29/20247/29/20244242（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 7
42、5 70) 97 第第6趟趟 3 8 12 26 53 61 (70 75) 87 97 第第7趟趟 3 8 12 26 53 61 70 (75) 87 97 7/29/20247/29/20244343（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 6
43、1第第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）977/29/20247/29/2024444411-4 11-4 从以下几个方面比较题从以下几个方面比较题从以下几个方面比较题从以下几个方面比较题11-211-2中各种排序算法。中各种排序算法。中各种排序算法。中各种排序算法。（1 1）最好
44、、最坏和平均情况下的时间复杂度；）最好、最坏和平均情况下的时间复杂度；）最好、最坏和平均情况下的时间复杂度；）最好、最坏和平均情况下的时间复杂度；（3 3）稳定性（对不稳定的算法给出一个简单的实）稳定性（对不稳定的算法给出一个简单的实）稳定性（对不稳定的算法给出一个简单的实）稳定性（对不稳定的算法给出一个简单的实例）；例）；例）；例）；（4 4）指出第）指出第）指出第）指出第1 1趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终趟排序结束后就能确定某个元素最终位置的算法。位置的算法。位置的算法。位置的算法。7/29/20247/29/202445
45、45（1）最好、最坏和平均情况下的时间复杂度：）最好、最坏和平均情况下的时间复杂度：简单选择排序简单选择排序: 三种情况下的时间复杂度都为三种情况下的时间复杂度都为O(n2)。直接插入排序：直接插入排序：最好情况下为最好情况下为O(n)；平均和最坏情况下为平均和最坏情况下为O(n2)。冒泡排序：冒泡排序：最好情况为最好情况为O(n)；最坏和平均情况下为最坏和平均情况下为O(n2)。快速排序：快速排序：最好和平均情况下为最好和平均情况下为O(nlog2n)；最坏情况下时间复杂度为最坏情况下时间复杂度为O(n2)。7/29/20247/29/20244646（3）稳定性：）稳定性：不稳定的是简单选
46、择排序和快速排序两种，其它是不稳定的是简单选择排序和快速排序两种，其它是稳定的。稳定的。实例：实例：3 3 1 简单选择排序过后变成了简单选择排序过后变成了 1 3 3， 3 4 3 快速排序之后变成了快速排序之后变成了3 3 4 7/29/20247/29/20244747（4）第一趟排序结束后就能确定某个元素最终位）第一趟排序结束后就能确定某个元素最终位置的算法：置的算法：简单选择排序：确定最小元素在第一位简单选择排序：确定最小元素在第一位冒泡排序：确定最大元素在最后一位冒泡排序：确定最大元素在最后一位快速排序：确立分割元素在中间快速排序：确立分割元素在中间7/29/20247/29/20244848最好最好最坏最坏平均平均最终位置最终位置稳定性稳定性简单选择简单选择排序排序O(n2)O(n2)O(n2)能能不稳定不稳定直接插入直接插入排序排序O(n)O(n2)O(n2)不能不能稳定稳定冒泡排序冒泡排序O(n)O(n2)O(n2)能能稳定稳定快速排序快速排序O(nlog2n)O(n2)O(nlog2n)能能不稳定不稳定7/29/20247/29/20244949
