数据结构面试常见问题

什么是数据结构？

数据结构是组织数据的一种方式，以便可以有效地使用数据。不同类型的数据结构适用于不同类型的应用程序，有些则高度专业化，适用于特定任务。例如，B 树特别适合数据库的实现，而编译器实现通常使用哈希表来查找标识符。

什么是线性和非线性数据结构？

线性：如果数据结构的元素形成序列或线性列表，则称其为线性。示例：数组。链表、堆栈和队列
非线性：如果节点的遍历本质上是非线性的，则称数据结构为非线性。示例：图形和树形。

可以对不同的数据结构执行哪些操作？

插入：在给定的数据项集合中添加新的数据项。
删除：从给定的数据项集合中删除现有数据项。
遍历：仅访问每个数据项一次，以便可以对其进行处理。
搜索：找出数据项的位置（如果它存在于给定的数据项集合中）。
排序：按某种顺序排列数据项，即在数字数据的情况下按升序或降序排列，在字母数字数据的情况下按字典顺序排列。

数组与链表有何不同？

数组的大小是固定的，而链接列表的大小是动态的。
在元素数组中插入和删除新元素的成本很高，而插入和删除都可以在链接列表中轻松完成。
链接列表上不允许随机访问。
链接列表的每个元素都需要为指针提供额外的内存空间。
数组具有更好的缓存位置，可以在性能方面产生相当大的差异。

什么是堆栈，在哪里可以使用？

堆栈是一种线性数据结构，其中用于访问元素的顺序为LIFO（后进先出）或FILO（先进后出）。堆栈的基本操作是：入栈，出栈，Peek

堆栈的应用：

使用堆栈对后缀转换进行中缀
后缀表达式的评估
使用堆栈反转字符串
在数组中实现两个堆栈
检查表达式中的平衡括号

什么是队列，它与堆栈有何不同，如何实现？

队列是一个线性结构，其顺序是先进先出（FIFO）以访问元素。主要是队列的基本操作：入队、出队、队头、队尾。

堆栈和队列之间的区别在于删除。在堆栈中，我们删除最近添加的项目；在队列中，我们删除最近最少添加的项目。队列和堆栈都可以使用数组和链表来实现。

什么是中缀、前缀、后缀符号？

中缀表示法：X + Y – 运算符写在其操作数之间。这是我们编写表达式的常用方式。表达式，例如

A * ( B + C ) / D
后缀表示法（也称为“逆波兰语表示法”）：X Y + 运算符在其操作数之后编写。上面给出的中缀表达式等效于

A B C + * D/
前缀表示法（也称为“波兰语表示法”）：+ X Y 运算符写在其操作数之前。上面给出的表达式等效于

/ * A + B C D

什么是链表，它的类型是什么？

链表是一种线性数据结构（如数组），其中每个元素都是一个单独的对象。列表的每个元素（即节点）都由两个项目组成 - 数据和对下一个节点的引用。链表类型：

单链表：在这种类型的链表中，每个节点都存储列表中下一个节点的地址或引用，最后一个节点的下一个地址或引用为 NULL。例如：

1->2->3->4->NULL
双链表：这里有两个与每个节点关联的引用，一个指向下一个节点，一个指向前一个节点。例如：

空<-1<->2<->3->空
圆形链表：圆形链表是一个链接列表，其中所有节点都连接在一起形成一个圆圈。末尾没有 NULL。循环链表可以是单循环链表或双循环链表。例如：

1->2->3->1 [最后一个节点的下一个指针指向第一个节点]

哪些数据结构用于图的 BFS 和 DFS？

队列用于 BFS
堆栈用于 DFS。DFS 也可以使用递归来实现（注意递归也使用函数调用堆栈）。

深度优先遍历简称DFS(Depth First Search)，广度优先遍历简称BFS(Breadth First Search)，它们是遍历图当中所有顶点的两种方式。

可以在每个节点中使用单个指针变量来实现双向链接吗？

可以使用单个指针来实现双向链表。

请参阅 XOR 链表 - 一种内存高效的双向链表。

https://www.geeksforgeeks.org/xor-linked-list-a-memory-efficient-doubly-linked-list-set-1/

应该使用哪种数据结构来实现 LRU 缓存？

我们使用两种数据结构来实现 LRU Cache。

使用双链表实现的队列。队列的最大大小将等于可用帧总数（高速缓存大小）。最近使用的页面将靠近后端，而最近最少的页面将靠近前端。
一个哈希，其中页码作为键，相应队列节点的地址作为值。

如何检查给定的二叉树是否为 BST？

如果二叉树的中序遍历是有序的，那么二叉树就是BST。这个想法是简单地进行中序遍历，并在遍历时跟踪先前的键值。如果当前键值更大，则继续，否则返回 false。

有关详细信息，请参阅检查二叉树是否为 BST 的程序。

https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

什么是 AVL 树？

AVL 树是平衡二叉查找树，增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。同理左旋是以某个节点为中心，将它沉入当前左子节点的位置，而让当前的右子节点作为新树的根节点，也称为逆时针旋转。

什么是红黑树？

红黑树是 1972 年发明的，称为对称二叉 B 树，1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色，可以红色或黑色。红黑树和 AVL 树类似，都是在进行插入和删除时通过旋转保持自身平衡，从而获得较高的查找性能。与 AVL 树相比，红黑树不追求所有递归子树的高度差不超过 1，保证从根节点到叶尾的最长路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转，更加高效地完成了插入和删除之后的自平衡调整。

红黑树在本质上还是二叉查找树，它额外引入了 5 个约束条件： ① 节点只能是红色或黑色。 ② 根节点必须是黑色。 ③ 所有 NIL 节点都是黑色的。 ④ 一条路径上不能出现相邻的两个红色节点。 ⑤ 在任何递归子树中，根节点到叶子节点的所有路径上包含相同数目的黑色节点。

这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在，则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。

AVL 树和红黑树的区别？

红黑树的平衡性不如 AVL 树，它维持的只是一种大致的平衡，不严格保证左右子树的高度差不超过 1。这导致节点数相同的情况下，红黑树的高度可能更高，也就是说平均查找次数会高于相同情况的 AVL 树。

在插入时，红黑树和 AVL 树都能在至多两次旋转内恢复平衡，在删除时由于红黑树只追求大致平衡，因此红黑树至多三次旋转可以恢复平衡，而 AVL 树最多需要 O(logn) 次。AVL 树在插入和删除时，将向上回溯确定是否需要旋转，这个回溯的时间成本最差为 O(logn)，而红黑树每次向上回溯的步长为 2，回溯成本低。因此面对频繁地插入与删除红黑树更加合适。

B 树和B+ 树的区别？

B 树中每个节点同时存储 key 和 data，而 B+ 树中只有叶子节点才存储 data，非叶子节点只存储 key。InnoDB 对 B+ 树进行了优化，在每个叶子节点上增加了一个指向相邻叶子节点的链表指针，形成了带有顺序指针的 B+ 树，提高区间访问的性能。

B+ 树的优点在于： ① 由于 B+ 树在非叶子节点上不含数据信息，因此在内存页中能够存放更多的 key，数据存放得更加紧密，具有更好的空间利用率，访问叶子节点上关联的数据也具有更好的缓存命中率。 ② B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子节点即可。而 B 树则需要进行每一层的递归遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有 B+树好。但是 B 树也有优点，由于每个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，访问也更迅速。

排序有哪些分类？

排序可以分为内部排序和外部排序，在内存中进行的称为内部排序，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序。

内部排序包括比较排序和非比较排序，比较排序包括插入/选择/交换/归并排序，非比较排序包括计数/基数/桶排序。

插入排序包括直接插入/希尔排序，选择排序包括直接选择/堆排序，交换排序包括冒泡/快速排序。

排序算法怎么选择？

数据量规模较小，考虑直接插入或直接选择。当元素分布有序时直接插入将大大减少比较和移动记录的次数，如果不要求稳定性，可以使用直接选择，效率略高于直接插入。

数据量规模中等，选择希尔排序。

数据量规模较大，考虑堆排序（元素分布接近正序或逆序）、快速排序（元素分布随机）和归并排序（稳定性）。

一般不使用冒泡。

想了解排序算法的朋友，可以参考博主专栏《程序员宝典--常用代码分享》

堆与栈

请说一说你理解的stack overflow

栈溢出概念： 栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。
栈溢出的原因：
局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。局部变量是存储在栈中的，因此这个很好理解。解决这类问题的办法有两个，一是增大栈空间,二是改用动态分配，使用堆（heap）而不是栈（stack）。
递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导致堆栈溢出。
指针或数组越界。这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。

请你回答一下栈和堆的区别，以及为什么栈要快

堆和栈的区别： 1、堆是由低地址向高地址扩展；栈是由高地址向低地址扩展 2、堆中的内存需要手动申请和手动释放；栈中内存是由OS自动申请和自动释放，存放着参数、局部变量等内存 3、堆中频繁调用malloc和free,会产生内存碎片，降低程序效率；而栈由于其先进后出的特性，不会产生内存碎片 4、堆的分配效率较低，而栈的分配效率较高
栈的效率高的原因： 栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的寄存器存储栈的地址，压栈和入栈有专门的指令执行；而堆是由C/C++函数库提供的，机制复杂，需要一些列分配内存、合并内存和释放内存的算法，因此效率较低。

请你说一说小根堆特点

堆是一棵完全二叉树（如果一共有h层，那么1~h-1层均满，在h层可能会连续缺失若干个右叶子）。

1）小根堆 若根节点存在左子女则根节点的值小于左子女的值；若根节点存在右子女则根节点的值小于右子女的值。
2）大根堆 若根节点存在左子女则根节点的值大于左子女的值；若根节点存在右子女则根节点的值大于右子女的值。

请你解释一下，内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法。并且说明heap和stack有什么区别。

通常我们定义一个基本数据类型的变量，一个对象的引用，还有就是函数调用的现场保存都使用内存中的栈空间；而通过new关键字和构造器创建的对象放在堆空间；程序中的字面量（literal）如直接书写的100、"hello"和常量都是放在静态区中。栈空间操作起来最快但是栈很小，通常大量的对象都是放在堆空间，理论上整个内存没有被其他进程使用的空间甚至硬盘上的虚拟内存都可以被当成堆空间来使用。栈是一种线形集合，其添加和删除元素的操作应在同一段完成。栈按照后进先出的方式进行处理。堆是栈的一个组成元素。

大顶堆怎么插入删除

插入: 在一个大顶堆之后插入新的元素可能会破坏堆的结构,此时需要找到新插入节点的父节点,对堆进行自下而上的调整使其变成一个大顶堆。 删除: 将堆的最后一个元素填充到删除元素的位置,然后调整堆结构构造出新的大顶堆

请你讲一下动态链表和静态链表的区别

静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。 动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

数组

请你回答一下Array&List，数组和链表的区别

数组的特点： 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。但数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。并且数组不利于扩展，数组定义的空间不够时要重新定义数组。
链表的特点： 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。不指定大小，扩展方便。链表大小不用定义，数据随意增删。
各自的优缺点数组的优点：
随机访问性强
查找速度快
数组的缺点:
插入和删除效率低
可能浪费内存
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展
链表的优点:
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。
链表的缺点: 不能随机查找，必须从第一个开始遍历，查找效率低

请问如何防止数组越界

由于数组的元素个数默认情况下是不作为实参内容传入调用函数的，因此会带来数组访问越界的相关问题防止数组越界： 1）检查传入参数的合法性。 2）可以用传递数组元素个数的方法，即：用两个实参，一个是数组名，一个是数组的长度。在处理的时候，可以判断数组的大小，保证自己不要访问超过数组大小的元素。 3）当处理数组越界时，打印出遍历数组的索引十分有帮助，这样我们就能够跟踪代码找到为什么索引达到了一个非法的值 4）Java中可以加入try{} catch(){ }

请回答数组和链表的区别，以及优缺点，另外有没有什么办法能够结合两者的优点

1.数组： 数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少插入和删除元素，就应该用数组。
2.链表： 链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表。
3.区别： （1）存储位置上：数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定；（2）存储空间上：链表存放的内存空间可以是连续的，也可以是不连续的，数组则是连续的一段内存空间。一般情况下存放相同多的数据数组占用较小的内存，而链表还需要存放其前驱和后继的空间。（3）长度的可变性：链表的长度是按实际需要可以伸缩的，而数组的长度是在定义时要给定的，如果存放的数据个数超过了数组的初始大小，则会出现溢出现象。（4）按序号查找时，数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)；（5）按值查找时，若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；（6）插入和删除时，数组平均需要移动n/2个元素，而链表只需修改指针即可（7）空间分配方面：数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败；即数组从栈中分配空间,，对于程序员方便快速,但自由度小。链表存储的节点空间只在需要的时候申请分配，只要内存中有空间就可以分配，操作比较灵活高效；即链表从堆中分配空间, 自由度大但申请管理比较麻烦。哈希表可以结合数组和链表的优点。

排序

1、请你来手写一下快排的代码，并说明其最优情况。

快速排序的最优情况是Partition每次划分的都很均匀,当排序的元素为n个,则递归树的深度为logn+1。在第一次做Partition的时候需对所有元素扫描一遍,获得的枢纽元将所有元素一分为二,不断的划分下去直到排序结束,而在此情况下快速排序的最优时间复杂度为nlogn。

2、请问求第k大的数的方法以及各自的复杂度是怎样的，另外追问一下，当有相同元素时，还可以使用什么不同的方法求第k大的元素

首先使用快速排序算法将数组按照从大到小排序，然后取第k个，其时间复杂度最快为O(nlogn) 使用堆排序，建立最大堆，然后调整堆，知道获得第k个元素，其时间复杂度为O(n+klogn) 首先利用哈希表统计数组中个元素出现的次数，然后利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大的数利用快排思想，从数组中随机选择一个数i，然后将数组分成两部分Dl,Dr，Dl的元素都小于i,Dr的元素都大于i。然后统计Dr元素个数，如果Dr元素个数等于k-1,那么第k大的数即为k，如果Dr元素个数小于k,那么继续求Dl中第k-Dr大的元素；如果Dr元素个数大于k,那么继续求Dr中第k大的元素。当有相同元素的时候，首先利用哈希表统计数组中个元素出现的次数，然后利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大的数，平均情况下时间复杂度为O(n)。

3、请你来介绍一下各种排序算法及时间复杂度

插入排序：对于一个带排序数组来说，其初始有序数组元素个数为1，然后从第二个元素，插入到有序数组中。对于每一次插入操作，从后往前遍历当前有序数组，如果当前元素大于要插入的元素，则后移一位；如果当前元素小于或等于要插入的元素，则将要插入的元素插入到当前元素的下一位中。 希尔排序：先将整个待排序记录分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，在对全体记录进行一次直接插入排序。其子序列的构成不是简单的逐段分割，而是将每隔某个增量的记录组成一个子序列。希尔排序时间复杂度与增量序列的选取有关，其最后一个值必须为1. 归并排序：该算法采用分治法；对于包含m个元素的待排序序列，将其看成m个长度为1的子序列。然后两两合归并，得到n/2个长度为2或者1的有序子序列；然后再两两归并，直到得到1个长度为m的有序序列。 冒泡排序：对于包含n个元素的带排序数组，重复遍历数组，首先比较第一个和第二个元素，若为逆序，则交换元素位置；然后比较第二个和第三个元素，重复上述过程。每次遍历会把当前前n-i个元素中的最大的元素移到n-i位置。遍历n次，完成排序。 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 选择排序：每次循环，选择当前无序数组中最小的那个元素，然后将其与无序数组的第一个元素交换位置，从而使有序数组元素加1，无序数组元素减1.初始时无序数组为空。 堆排序：堆排序是一种选择排序，利用堆这种数据结构来完成选择。其算法思想是将带排序数据构造一个最大堆（升序）/最小堆（降序），然后将堆顶元素与待排序数组的最后一个元素交换位置，此时末尾元素就是最大/最小的值。然后将剩余n-1个元素重新构造成最大堆/最小堆。各个排序的时间复杂度、空间复杂度及稳定性如下：

4、请问海量数据如何去取最大的k个

1.直接全部排序（只适用于内存够的情况） 当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出topK个数据，所以该方法并不十分高效，不建议使用。
2.快速排序的变形（只使用于内存够的情况） 这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index>K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回TopK个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。
3.最小堆法这是一种局部淘汰法。 先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。
4.分治法 将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下NK个数据，如果内存不能容纳NK个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。
5.Hash法 如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。

6、谈一谈，如何得到一个数据流中的中位数？

数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。数组是最简单的容器。如果数组没有排序，可以用 Partition函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。排序的链表时另外一个选择。我们需要O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。

7、对一千万个整数排序,整数范围在[-1000,1000]间,用什么排序最快?

在以上的情景下最好使用计数排序,计数排序的基本思想为在排序前先统计这组数中其它数小于这个数的个数,其时间复杂度为O(n+k),其中n为整数的个数,k为所有数的范围,此场景下的n>>k,所以计数排序要比其他基于的比较排序效果要好。

8、堆排序的思想

将待排序的序列构成一个大顶堆,这个时候整个序列的最大值就是堆顶的根节点,将它与末尾节点进行交换,然后末尾变成了最大值,然后剩余n-1个元素重新构成一个堆,这样得到这n个元素的次大值,反复进行以上操作便得到一个有序序列。

9、topK给出3种解法

1）局部淘汰法 – 借助“冒泡排序”获取TopK思路：

（1）可以避免对所有数据进行排序，只排序部分；

（2）冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK。

时间复杂度空间复杂度：

（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)。

（2）空间复杂度：O(K)，用来存放获得的topK，也可以O(1)遍历原数组的最后K个元素即可。

2）局部淘汰法 – 借助数据结构"堆"获取TopK思路： （

1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）。

（2）我们使用小顶堆来实现。

（3）取出K个元素放在另外的数组中，对这K个元素进行建堆。

（4）然后循环从K下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后重新调整为小顶堆。

（5）循环完毕后，K个元素的堆数组就是我们所需要的TopK。

时间复杂度与空间复杂度：

（1）时间复杂度：每次对K个元素进行建堆，时间复杂度为：O(KlogK)，加上N-K次的循环，则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)，其中K为想要获取的TopK的数量N为总数据量。

（2）空间复杂度：O(K)，只需要新建一个K大小的数组用来存储topK即可

3）分治法 – 借助”快速排序“方法获取TopK思路：

（1）比如有10亿的数据，找处Top1000，我们先将10亿的数据分成1000份，每份100万条数据。

（2）在每一份中找出对应的Top1000，整合到一个数组中，得到100万条数据，这样过滤掉了999%%的数据。

（3）使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。

（4）如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Si和Sj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序

（5）如此递归下去即可获得TopK。

时间复杂度与空间复杂度：

（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但是分治法我们会使用多核多机的资源，比如我们有S个线程同时处理。则时间复杂度为：O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)。所以，总时间复杂度大约为O(MN+(N/S)logK) 。

（2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)。