数据结构面试题整理学生收藏

发布网友 发布时间：2023-06-21 15:39

我来回答

共2个回答

热心网友 时间：2024-04-06 11:58

面试真题数据结构面试题整理题目+答案

一、什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

二、解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

三、头指针和头结点的区别?

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

四、线性结构的特点

(1)集合中必存在唯一的一个"第一个元素"；

(2)集合中必存在唯一的一个"最后的元素"；

(3)除最后元素之外，其它数据元素均有唯一的"后继"；

(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

五、数组和链表的区别?

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

六、单链表结构和顺序存储结构的区别?

当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O(n^2)，而链式存储结构确定i位置的指针后，其时间复杂度仅为O(1)。由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受*。

七、栈和队列的区别

队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

栈是只能在表尾进行插入和删除操作的线性表。附于播入到栈的元素据，“后进先出”的规则处理，插入和删除操作都在栈顶进行。

一由于进栈和出栈都是在栈顶进行， 所以要有一个size变量

来记录当前栈的大小， 当进栈时size不能超过数组长度，

size+1， 出栈时栈不为空， size-1。

八、介绍一下字符串匹配算法：

朴素的匹配算法和KMP算法

1.BF算法(BruteForce)

·目标串t(待匹配串)

·模式串p(短的那个串)

①t的第一个字符和S的第一个比较， 相等则继续t-2VSp-2， 相等则继续t-3VSp 

②不等则t-1VSp-2， t-2VSp-3

2.KMP算法：快速从主串找到子串

①上下子串前缀匹配

②找到公共前后缀(取最长且小于比较的上下字串长度)

(3将下面的p子串前缀移动到后缀位置

Brute-Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等， 但最后一个字符比较不相等时， 主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退，从而可以大大提高效率。

九、深度优先搜索和广度优先搜索是如何实现的?

深度优先搜索：(1)访问起始点v0

(2)若v0的第一个邻接点没有被访问过，则深度遍历该邻接点；

(3)若v0的第一个邻接点已经被访间，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止

广度优先搜索：(1)访问起始点v0

(2)依次遍历v0的所有未访问过得邻接点

(3)再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止

十、如何构造哈夫曼树?

找w最小求和，再找w最小；左小右大；构造结束后，左0右1

十一、最小生成树

最小生成树是要找到最小的边可以把所有的节点都连接起来，而最短路径是

要求某个节点到其余节点的最短的路径。

最小生咸树：

在一给定的无向图G=(V，E)中，(u，v)代表连接顶点u与顶点v的边(即)，而w(u，v)代表此边的权重，若存在T为E的子集(即)且为无循环图，使得w(T)最小，则此T为G的最小生成树。

w(t)=w(u，u)

最小生成树其实是最小(u，u)et

普里姆(prim) 算法的基本思想为：顶点集到其他点权值最小边， 加入新的顶点集，再找边…直到遍历所有点

从联通网络N={V，E}中某一顶点u0出发，选择与它关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的所有顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。

克鲁斯卡尔(kruskal) 算法的基本思想为：依次选择最小边， 使得无环且所有点遍历结束

假设有一个有n个顶点的联通网络N={V，E]，初试时建立一个只有n个顶点，没有边的非连通图T，T中每个顶点都看作是一个联通分支，从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到T中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。

十二、最短路径的算法

Dijkstra时间复杂度为O(n~2)

Fly od时间复杂度为O(n^3) 空间复杂度为O(n^2) ；

最短路径：用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

迪杰斯特拉(dij astra) 算法

经典的单源最短路径算法主要是其采用的动态规划思想.

弗洛伊德(floyd) 算法

经典的求任意顶点之间的最短路径，采用贪心思想。

十三、介绍一下拓扑排序以及是如何实现的?

拓扑排序的步骤：

(1)在有向图中任意选择一个没有前驱的节点输出

(2)从图中删去该节点以及与它相连的边

(3)重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。

十四、简述各种查找方法

查找分为静态查找表和动态查找表

静态查找表包括：顺序查找、折半查找、分块查找；

动态查找包括：二叉排序树和平衡二叉树。

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

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

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

(4)二又排序树：二叉排序树的定义为：一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树

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

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

十五、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

(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，当满足下面特点时称之为堆：让此序列排列成b

完全二叉树，该树具有以下特点，该树中任意节点均

大于或小于其左右孩子，此树的根节点为最大值或者

最小值。优点是：对大文件效率明显提高，但对小文件

效率不明显。时间复杂度为O(nlog2n) ， 空间复杂度为O(1)。

十六、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

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

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

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

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

“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O(n^2)，空间复杂度为O(1)。

热心网友 时间：2024-04-06 11:58

面试真题数据结构面试题整理题目+答案

一、什么是数据结构?

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

二、解释一下顺序存储与链式存储

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

三、头指针和头结点的区别?

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

四、线性结构的特点

(1)集合中必存在唯一的一个"第一个元素"；

(2)集合中必存在唯一的一个"最后的元素"；

(3)除最后元素之外，其它数据元素均有唯一的"后继"；

(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

五、数组和链表的区别?

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

六、单链表结构和顺序存储结构的区别?

当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O(n^2)，而链式存储结构确定i位置的指针后，其时间复杂度仅为O(1)。由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受*。

七、栈和队列的区别

队列是允许在一段进行插入另一端进行删除的线性表，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。

栈是只能在表尾进行插入和删除操作的线性表。附于播入到栈的元素据，“后进先出”的规则处理，插入和删除操作都在栈顶进行。

一由于进栈和出栈都是在栈顶进行， 所以要有一个size变量

来记录当前栈的大小， 当进栈时size不能超过数组长度，

size+1， 出栈时栈不为空， size-1。

九、介绍一下字符串匹配算法：

朴素的匹配算法和KMP算法

1.BF算法(BruteForce)

·目标串t(待匹配串)

·模式串p(短的那个串)

①t的第一个字符和S的第一个比较， 相等则继续t-2VSp-2， 相等则继续t-3VSp 

②不等则t-1VSp-2， t-2VSp-3

2.KMP算法：快速从主串找到子串

①上下子串前缀匹配

②找到公共前后缀(取最长且小于比较的上下字串长度)

(3将下面的p子串前缀移动到后缀位置

Brute-Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等， 但最后一个字符比较不相等时， 主串的比较位置需要回退。KMP算法在上述情况下，主串位置不需要回退，从而可以大大提高效率。

十、深度优先搜索和广度优先搜索是如何实现的?

深度优先搜索：(1)访问起始点v0

(2)若v0的第一个邻接点没有被访问过，则深度遍历该邻接点；

(3)若v0的第一个邻接点已经被访间，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止

广度优先搜索：(1)访问起始点v0

(2)依次遍历v0的所有未访问过得邻接点

(3)再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止

十一、如何构造哈夫曼树?

找w最小求和，再找w最小；左小右大；构造结束后，左0右1

十二、最小生成树

最小生成树是要找到最小的边可以把所有的节点都连接起来，而最短路径是

要求某个节点到其余节点的最短的路径。

最小生咸树：

在一给定的无向图G=(V，E)中，(u，v)代表连接顶点u与顶点v的边(即)，而w(u，v)代表此边的权重，若存在T为E的子集(即)且为无循环图，使得w(T)最小，则此T为G的最小生成树。

w(t)=w(u，u)

最小生成树其实是最小(u，u)et

普里姆(prim) 算法的基本思想为：顶点集到其他点权值最小边， 加入新的顶点集，再找边…直到遍历所有点

从联通网络N={V，E}中某一顶点u0出发，选择与它关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的所有顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。

克鲁斯卡尔(kruskal) 算法的基本思想为：依次选择最小边， 使得无环且所有点遍历结束

假设有一个有n个顶点的联通网络N={V，E]，初试时建立一个只有n个顶点，没有边的非连通图T，T中每个顶点都看作是一个联通分支，从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到T中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。

十三、最短路径的算法

Dijkstra时间复杂度为O(n~2)

Fly od时间复杂度为O(n^3) 空间复杂度为O(n^2) ；

最短路径：用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

迪杰斯特拉(dij astra) 算法

经典的单源最短路径算法主要是其采用的动态规划思想.

弗洛伊德(floyd) 算法

经典的求任意顶点之间的最短路径，采用贪心思想。

十四、介绍一下拓扑排序以及是如何实现的?

拓扑排序的步骤：

(1)在有向图中任意选择一个没有前驱的节点输出

(2)从图中删去该节点以及与它相连的边

(3)重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。

十五、简述各种查找方法

查找分为静态查找表和动态查找表

静态查找表包括：顺序查找、折半查找、分块查找；

动态查找包括：二叉排序树和平衡二叉树。

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

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

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

(4)二又排序树：二叉排序树的定义为：一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树

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

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

十六、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

(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，当满足下面特点时称之为堆：让此序列排列成b

完全二叉树，该树具有以下特点，该树中任意节点均

大于或小于其左右孩子，此树的根节点为最大值或者

最小值。优点是：对大文件效率明显提高，但对小文件

效率不明显。时间复杂度为O(nlog2n) ， 空间复杂度为O(1)。

十六、简述各种排序算法(一)

内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。

其中插入排序包括：直接插入排序、折半插入排序、希尔排序；

选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。

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

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

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

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

“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O(n^2)，空间复杂度为O(1)。