计算机考研复试面试常问问题 数据结构篇（下）

使用前需知（拒绝白嫖，如果对你有帮助，你只需点个赞就行）：

注意：有人在闲鱼上盗卖我的资料，而且还有很多同学买了，请各位擦亮双眼，我是整理出来免费给大家的！ 

大家请多和评论，这样后面的同学更容易百度到，不至于被人盗卖，我就不加水印影响大家使用了！

第一次整理，度不好控制，有不好的地方希望大家理解，后面可能会改进，造福今年之后的同学们！ 

需要pdf直接打印版，可在公众号”程序员宝藏“回复复试上岸获取(会持续更新)

在复习过程中，我用心查阅并整理了在考研复试面试中可能问到的大部分问题，并分点整理了答案，可以直接理解背诵并加上自己的语言润色!极力推荐打印下来看，效率更高！

声明：一些边边角角的没有收集，毕竟是考研面试，不是笔试，这样也能减轻大家的负担！

此系列一共有8篇：编程语言篇**|数据结构篇|操作系统篇|组成原理篇|计算机网络篇|数据库篇|软件工程篇|计算机专业英语篇**(还未全部完成,敬请期待,你们的支持和关注是我最大的动力!)

个人整理，不可用于商业用途，转载请注明出处。

需要408电子书2021版，可在公众号”程序员宝藏“回复408电子书获取

需要408初试视频2021版，可在公众号”程序员宝藏“回复408视频获取

需要复试机试视频，可在公众号”程序员宝藏“回复机试必过获取

加油，大家都可以上岸！！！让我们一起努力！！！

第五章、树与二叉树

快速唤起记忆知识框架：

19.树与二叉树的相关概念？

树是非线性结构，其元素之间有明显的层次关系。在树的结构中，每个节点都只有一个前件称为父节点，没有前件的节点为树的根节点，简称为树的根；每个节点可以有多个后件成为节点的子节点，没有后件的节点称为叶子节点。

在树的结构中，一个节点所拥有的子节点个数称为该节点的度，树中最大的节点的度为树的度，树的最大的层次称为树的深度

二叉树：二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。与树相似，二叉树也以递归的形式定义。二叉树是n (n >=0) 个结点的有限集合：

1)或者为空二叉树，即n=0 。
2)或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有
一棵子树，也要区分它是左子树还是右子树

满二叉树：满二叉树是指除了最后一层外其他节点均有两颗子树。

完全二叉树：完全二叉树是指除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点

二叉树的存储：二叉树可以用链式存储结构来存储，满二叉树和完全二叉树可以用顺序存储结构来存储

二叉树的遍历：二叉树有先序遍历（根左右），中序遍历（左根右）和后续遍历（左右根）；还有层次遍历，需要借助一个队列。

三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n) 。在递归遍历
中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n 个结点且深度为n 的单支树，遍历算法的空间复杂度为O(n) 。

20.如何由遍历序列构造一棵二叉树？

1)由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中
序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

2)由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。
因为后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子
序列，然后采用类似的方法递归地进行划分，进而得到一棵二叉树。

3）由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。需要注意的是，若只知道二叉树的先序序列和后序序列，则无法唯一确定一棵二叉树。

21.线索二叉树的概念？

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

**注意：**线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

22.树的存储结构？

1.双亲表示法：

这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示
其双亲结点在数组中的位置。

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结点的
双亲结点，但求结点的孩子时需要遍历整个结构。

2.孩子表示法：

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n 个结点
就有n 个孩子链表（叶子结点的孩子链表为空表），这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。

3.孩子兄弟表示法：

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每
个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）

这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查
找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。

23.二叉排序树

1.二叉排序树的定义：
二叉排序树（也称二叉查找树）或者是一棵空树，或者是具有下列特性的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树。
   根据二叉排序树的定义，左子树结点值＜根结点值＜右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

2.二叉排序树的查找：

二叉排序树的查找是从根节点开始的，延某个分支逐层向下比较的过程。若二叉树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根的右子树上查找。这显然是一个递归的过程。

24.平衡二叉树

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1, 将这样的二叉树称为平衡二叉树(Balanced Binary Tree), 简称平衡树。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1 、0 或1 。因此，平衡二叉树可定义为或者是一棵空
树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子
树的高度差的绝对值不超过1 。

25.哈夫曼树和哈夫曼编码：

2.哈夫曼树的构造

给定n 个权值分别为W1,W2…， Wn 的结点，构造哈夫曼树的算法描述如下：

1. 将这n 个结点分别作为n 棵仅含一个结点的二叉树，构成森林F 。
2. 构造一个新结点，从F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3. 从F 中删除刚才选出的两棵树，同时将新得到的树加入F 中。
4. 重复步骤2) 和3)’直至F 中只剩下一棵树为止。

从上述构造过程中可以看出哈夫曼树具有如下特点：

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
2. 构造过程中共新建了n — 1 个结点（双分支结点），因此哈夫曼树的结点总数为2n -1 。
3. 每次构造都选择2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为1 的结点。

3.哈夫曼编码：

在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。
若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。

由哈夫曼树得到哈夫曼编码是很自然的过程。首先，将每个出现的字符当作一个独立的结点，
其权值为它出现的频度（或次数），构造出对应的哈夫曼树。显然，所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根至该字符的路径上边标记的序列，其中边标记为0 表示“转向左孩子”，标记为1 表示“转向右孩子“。

第六章、图

快速唤起记忆知识框架：

26.图的一些相关定义

这个比较基础，忘了的自己去看看把，学过离散的应该比较熟悉。

27.图的存储结构:

1.邻接矩阵法：

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边
的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。有向图、无向图和网对应的邻接矩阵实例图如下：

适合稠密图。

2.邻接表法：

当一个图为稀疏图时，使用邻接矩阵法显然要浪费大量的存储空间，而图的邻接表法结合了
顺序存储和链式存储方法，大大减少了这种不必要的浪费。所谓邻接表，是指对图G 中的每个顶点V建立一个单链表，第i个单链表中的结点表示依附于顶点v, 的边（对于有向图则是以顶点v, 为尾的弧），这个单链表就称为顶点vi 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

3.十字链表法：

十字链表法是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。

4.邻接多重表：

邻接多重表是无向图的另一种链式存储结构。
在邻接表中，容易求得顶点和边的各种信息，但在邻接表中求两个顶点之间是否存在边而对
边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率较低。与十字链表类似，在邻接多重表中，每条边用一个结点表示，每个顶点也用一个结点表示。

28.图的遍历(代码请自己写)

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访
问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历比树的遍历要复杂得多，因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[] 来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

1.广度优先搜索(Breadth-First-Search, BFS)：

类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点V, 接着由V出发，依次访问V 的各个未访问过的邻接顶点W1, W2,… Wn, 然后依次访问W1, W2,…, Wn 的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为初始点，重复上述过程。Dijkstra源最短路径算法和Prim 最小生成树算法也应用了类似的思想。

2.深度优先搜索（Depth-First-Search, DFS):

它的基本思想如下：首先访问图中某一起始顶点V, 然后由v 出发，访问与v 邻接且未被访问的任一顶点W1, 再访问与W1邻接且未被访问的任一顶点W2……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

29.最小生成树和最短路径：

这四个算法请自己去翻书或百度，这是图的比较经典的应用。

迪杰斯特拉（dijkstra）算法：迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止，迪杰斯特拉算法要求边的权值不能为负权。

弗洛伊德（Floyd）算法：弗洛伊德算法是经典的求任意顶点之间的最短路径，其边的权值可为负权，该算法的时间复杂度为O(N^{3),空间复杂度为O（N}2）。

普里姆（prim）算法：用来求最小生成树，其基本思想为：从联通网络N={V,E}中某一顶点u0出发，选择与他关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的所有顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。

克鲁斯卡尔（kruskal）算法：用来求最小生成树，其基本思想为：设有一个有N个顶点的联通网络N={V,E},初试时建立一个只有N个顶点，没有边的非连通图T，T中每个顶点都看作是一个联通分支，从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到T中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。

30.关键路径：

AOE和AOV偏理解以及手动模拟，也自己去看吧。

第七章、查找

快速唤起记忆知识框架：

31.对各种查找方法的概括？

查找分为静态查找表和动态查找表；静态查找表包括：顺序查找、折半查找、分块查找；动态查找包括：二叉排序树和平衡二叉树。

（1）顺序查找：把待查关键字key放入哨兵位置（i=0），再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置i（i!=0）则查找成功，设置哨兵的位置是为了加快执行速度。他的时间效率为O（n），其特点是：结构简单，对顺序结构和连式结构都适用，但是查找效率太低。

（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界<=查找范围的下界。

（3）分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，也就是保证块间是有序的（但是子表内不一定有序），把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。他的特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。

（4）二叉排序树：二叉排序树的定义为：或者是一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树。在查找时可以进行动态的插入，插入节点要符合二叉排序树的定义，这也是动态查找和静态查找的区别，静态查找不能进行动态插入。

（5）平衡二叉树：平衡二叉树又称为AVL树，它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。

平衡因子：是指左子树的高度减去右子树的高度，它的值只能为1,0，-1

如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括4中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。

32.B树和B+树：

1.B 树，又称多路平衡查找树， B 树中所有结点的孩子个数的最大值称为B 树的阶，通常用m
表示。一棵m 阶B 树或为空树，或为满足如下特性的m 叉树：

1. 树中每个结点至多有m 棵子树，即至多含有m-1 个关键字。
2. 若根结点不是终端结点，则至少有两棵子树。
3. 除根结点外的所有非叶结点至少有「m/2] 棵子树，即至少含有「m/2]- 1 个关键字。
4. 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似千折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B 树是所有结点的平衡因子均等于0 的多路平衡查找树。

2.B+树是应数据库所需而出现的一种B 树的变形树。

一棵m 阶的B+树需满足下列条件：

1. 每个分支结点最多有m 棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有「m/2]棵子树。
3. 结点的子树个数与关键字个数相等。
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，
   并且相邻叶结点按大小顺序相互链接起来。
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中
   关键字的最大值及指向其子结点的指针。

m 阶的B+树与m 阶的B 树的主要差异如下：

1. 在B+树中，具有n 个关键字的结点只含有n 棵子树，即每个关键字对应一棵子树；而在
   B 树中，具有n 个关键字的结点含有n+1棵子树。
2. 在B+树中，每个结点（非根内部结点）的关键字个数n 的范围是「m/2]<=n<= m (根结点：
   1<=n<=m); 在B 树中，每个结点（非根内部结点）的关键字个数n 的范围是「m/2]-1<=n<=
   m-1 。
3. 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只
   含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4. 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点
   中；而在B 树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

32.哈希表的概念、哈希函数的构造方法、哈希冲突的解决办法？

哈希表又称为散列表，是根据关键字码的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希函数的构造方法包括：直接定址法，除留余数法，数字分析法，平方取中法，折叠法，随机数法

（1）直接定址法：取关键字的某个线性函数值作为散列地址，H(key)=a*key+b。

（2）除留余数法：取关键字对p取余的值作为散列地址，其中p<m,即H(key)=key%p (p<m)。

（3）数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列的地址，适用于所有关键字都已知的情况。

（4）平方取中法：对关键字求平方，再取结果中的中间几位作为散列地址。

（5）折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和作为散列地址。适用于关键字位数较多，且关键字中每一位上数字分布大致均匀。

（6）随机数法：选择一个随机函数，把关键字的随机函数值作为散列地址。适合于关键字的长度不相同时。

哈希冲突的解决方法包括：开放定址法和拉链法，当冲突发生时，使用某种探测技术形成一个探测序列，然后沿此序列逐个单单元查找，直到找到该关键字或者碰到一个开放的地址为止，探测到开放的地址表明该表中没有此关键字，若要插入，则探测到开放地址时可将新节点插入该地址单元。其中开放定址法包括：线性探查法，二次探查法，双重散列法

（1）线性探查法：基本思想，探查时从地址d开始，首先探查T[d],在探查T[d+1]…直到查到T[m-1]，此后循环到T[0],T[1]…直到探测到T[d-1]为止。

（2）二次探查法：基本思想，探查时从地址d开始，首先探查T[d],再探查T[d+1^2],T[d+22]…等，直到探查到有空余地址或者探查到T[d-1]为止，缺点是无法探查到整个散列空间。

（3）双重散列法：基本思想，使用两个散列函数来确定地址，探查时从地址d开始，首先探查T[d],再探查T[d+h1(d)],T[d+2*h1(d)]…

链接法：将所有关键字为同义词的节点链接在同一个单链表中，若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组，凡是散列地址为i的节点均插入到头指针为i的单链表中。

第八章、排序

快速唤起记忆知识框架：

33.对各种内部排序的概括与总结？

排序：是指把一个任意元素的序列排列成一个按关键字key有序的序列。内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。其中插入排序包括：直接插入排序、折半插入排序、希尔排序；选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

（1）直接插入排序（稳定）：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。时间复杂度为：O（n^2）,空间复杂度为O（1）

（2）折半插入排序（稳定）：基本思想为：设置三个变量low high mid，令mid=(low+high)/2,若a[mid]>key,则令high=mid-1,否则令low=mid+1,直到low>high时停止循环，对序列中的每个元素做以上处理，找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移，因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是：比较次数大大减少。

（3）希尔排序（不稳定）：基本思想为：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为O（1）。

（4）简单选择排序（不稳定）：基本思想为：将序列分为2部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现起来特别简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为O（n^2），空间复杂度为O（1）。

（5）堆排序（不稳定）：设有一个任意序列，k1,k2,…,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。优点是：对大文件效率明显提高，但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。

（6）冒泡排序（稳定）：基本思路为：每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O（n^2）,空间复杂度为O（1）。

（7）快速排序（不稳定）：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O（log2n）.

（8）归并排序（稳定）：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O（nlogn）,空间复杂度和待排序的元素个数相同。

（9）基数排序：时间复杂度为：对于n个记录进行链式基数排序的时间复杂度为O（d(n+rd)）,其中每一趟分配的时间复杂度为O(n),回收的时间复杂度为O（rd）。

各种排序的总结表格如下：

直接插入排序、冒泡排序和简单选择排序是基本的排序方法，它们主要用于元素个数n不是很大(n < 10000) 的情形。

对于中等规模的元素序列(n <=1000), 希尔排序是一种很好的选择。

对于元素个数n 很大的情况，可以采用快排、堆排序、归并排序或基数排序，其中快排和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法。