海量数据处理：如何从10亿个数中，找出最大的10000个数？（top K问题）

问题：有10亿个不重复的数字，内存中只能放进1万个数，怎么找到最大的1万个数字？此题多数互联网公司在面试的时候都会问到，这里简单总结一下。我将在下面介绍一些基本的海量数据处理的方法，供大家参考。需要明确的一点是，现实情况复杂多变，所以对于海量数据处理这样大的主题，是不可能用一篇博客就说清楚的。但方法论可以一通百通，我们通过一些已经被无数次实验证明有效的方法，就能大致理解对此类问题的解决思路，之后在面临新的问题时，至少能找到一个大致的方向。首先，被问到这题应该先询问数据规模与数据分布。如果数据规模比较小，在千数量级，采用O（nlgn）的快排或大顶堆取前K个即可。如果数据为整形，且分布范围不大，可以考虑计数排序，在线性时间中求解。其次，如果不是上面讨论的情况，就是大规模一般情况。数据集可能在亿数量级，此时有可能数据都没有办法全部加载到内存中，此时通常比较好的方案是：分治、Trie树/hash、小顶堆，即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树或Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有topK中求出最终的topK。方法一：将数据全部排序将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个int类型占4个字节，10亿个数就要占用3.7G的存储空间，对于一些可用内存小于3.7G的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。只能锁这是一个方法，但是实际可行性不高。方法二：局部淘汰法维护一个10000长度的数组a[]，先读取源数据中的前10000个放入数组，对该数组进行升序排序，再依次读取源数据第10000个以后的数据，和数组中最小的元素（a[0]）比较，如果小于a[0]直接pass，大于的话，就丢弃最小的元素a[0]，利用二分法找到其位置，然后该位置前的数组元素整体向前移位，直到源数据读取结束。最后遍历完这10亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。这比方法一效率会有很大的提高，但是当K的值较大的时候，长度为K的数据整体移位，也是非常耗时的。方法三：常规解法,利用最小堆的原理(时间复杂度为O(N*logK))(掌握)首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），最小堆的堆顶元素就是最大K个数中的最小的一个。之后读取后续数字，每次扫描一个数据X，如果X比堆顶元素小，则不需要改变原来的堆。如果X比堆顶元素大，那么用X替换堆顶元素，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。全部的时间复杂度为O(N*logK)。这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次。甚至还可以运用多线程技术，把所有10亿个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。下面我使用堆排序的思想写一个寻找数组中最大的K个数的模板，仅供参考：方法四：分治法+快速排序原理(时间复杂度O(N*logK)(掌握)假设N个数存储在数组S中，从数组中随机找最大的K个数，将数组分成两部分SMax和SMin。SMax中的元素大于等于X,SMin中的元素小于X。出现如下两种情况：(1)若SMax组的个数大于或等于K，则继续在SMax分组中找取最大的K个数字。(2)若SMin组中的数字小于K，其个数为T，则继续在SMin中找取K-T个数字。一直这样递归下去，不断把问题分解成小问题，平均时间复杂度为O(N*logK)。上面这个思路具体可以参考剑指Offer40.最小的k个数这道题，这道题是寻找最小的K个数，但是思想都是一样的。这里我给出个模板，仅供参考：上面的思路在数据规模比较小的时候完全可以和方法一相互替换使用，但是当数据量比较大的时候，这个方法不能直接使用，但是方法一可以直接使用，而此方法不能直接使用的原因就是数据没有办法一次性加载到内存中。因此我们可以考虑配合分治法，即：将10亿个数据分成100份，每份1000万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000（100万）个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉10亿数据里面99%的数据。一些经常被提及的该类问题这里再列举一些常见的海量数据处理的问题以及给出对应的解决方案，仅供参考：（1）有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。这个还是典型的Topk问题，解决方案如下：方案1：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件中。这样新生成的文件每个的大小大约也1G（假设hash函数是足够离散的）。找一台内存在2G左右的机器，依次用hash_map(query,query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。最后对这10个文件进行归并排序即可。方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。方案3：与方案1类似，但在做完hash分成多个文件后，可以采用大数据分布式的架构来处理（比如MapReduce），最后再进行合并。（2）有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。（3）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？方案1：分治法。粗略计算得知，每个文件的大小为50*10^8×64=320G，单单一个文件就远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。具体策略如下：遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M（假设hash函数足够离散）。遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0-b0,a1-b1,...,a999-b999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。方案2：使用布隆过滤器。如果允许有一定的错误率，可以使用Bloomfilter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloomfilter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloomfilter，如果是，那么该url应该是共同的url。（4）现有两个各有20亿行的文件，每一行都只有一个数字，求这两个文件中数字的交集？这个题的如果换成给定两个整型数组让求两个数组（nums1,nums2）的交集该如何做呢？这是LeetCode第349题，解决方法有很多，这里我提供两种解法，仅供参考：解法1：由于给定的数据有限，所以可以不用考虑内存装不装的下的问题，因此这里可以直接先把nums1中的所有元素全部添加到集合set1中，然后遍历nums2，判断在nums2中的元素在集合set1中是否存在，如果存在，说明有交集，就把他添加到结果中。解法2：对两个数组先升序排序，排序之后设置两个指针分别从nums1和nums2数组首地址开始遍历数组，比那里过程中会有以下3种情况：1.nums1[i]<nums2[j]，此时应该将i继续向后移动,j不动，因为nums1[i]已经比nums2[j]小了，在他们之间不可能找到相等的数2.nums1[i]>nums2[j]，情况正好相反，此时移动j就好了，i不动，道理类似3.nums1[i]=nums2[j]，出现了交集，将此值加入结果，并且i,j同时向后移动下面分别给出代码实现，仅供参考！有了这两种解题思路之后，尤其是方法2的思路之后，现在我们遇到最大的困难就是大文件无法全部加载到内存中，这个问题的解决办法还是分治法，即先使用外排序分别对两个文件进行分隔排序，比如分隔成1000个小文件，总之排序完成会得到两个有序的文件，之后同时遍历这两个文件就可以了，每次遍历加载文件一部分数据，遍历时采取的方法就如方法2所示。（5）海量日志数据，提取出某日访问网站次数最多的那个IP。粗略估算一下便知，就拿32位的IPV4来说，最多可以有2^32（42亿）种取值情况，所以不能完全加载到内存中处理；可以考虑采用分而治之的思想：按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中，每个小文件最多包含420万个IP地址（hash函数理想的情况下）对于每一个小文件，可以构建一个IP为key，出现的次数为value的HashMap，同时记录当前出现次数最多的那个IP地址，通过HashMap可以很容的得到该文件中次数最个IP每个文件一个最大次数Ip，汇总起来可以得到1024个IP，再依据常规的排序算法得出总体上出现次数最多的IP。（6）10亿个整数（有重复），找出重复次数最多的100个整数。解决思路：通过hash取模的方式将大文件分成电脑可以直接完全加载计算的小份文件，比如10亿个数分成1000份；在每一小份文件中排序，统计出出现次数最多的100个数；将每个文件中出现次数最多的100个数拿出来放到一起使用上文所说的快排思路或小顶堆取出其前100个即可。（7）海量数据排序问题：一个文件中有9亿条不重复的9位整数,对这个文件中数字进行排序方法一、数据库排序法。将文本文件导入到数据库中,让文本文件导入到数据库中,让数据库进行索引排序操作后提取数据到文件.该种方法虽然操作简单,方便,但是运算速度较慢,而且对数据库设备要求比较高.方法二、分治法。通过Hash法将9亿条数据分为20段,每一段大约5000万条,大约需要占用500万*4B=200MB空间,在文件中依次搜索0~5000万,50000001~1亿,,,,,,,将排序的结果存入文件,该方法要装满9位整数,一共需要20次,所以一共要进行20次排序,需要对文件进行20次读操作.该方法虽然缩小了每次使用的内存空间大小,但是编码复杂,速度也慢.方法三、位图法。考虑到最大的9位整数为999999999,由于9亿条数据是不重复的,如果这些数据都还是正整数的话，那么可以申请一个10亿个元素的位数组bitset表示0~999999999,结点中用0表示没有这个数,1表示存在这个数,判断0或1只用一个bit存储就够了,而声明一个可以包含9位整数的bit数组,一共需要10亿bit/8/1024/1024≈120MB内存,把内存中的数组全部初始化为0,读取文件中的数据,并将数据放入内存.比如读到一个数据为314332897这个数据,那就先在内存中找到314332897这个bit,并将bit值置为1,遍历整个bit数组,将bit为1的数组下标存入文件,最终得到排序的内容.参考【1】xiaoding133.【编程之美】读书笔记：寻找最大的K个数.CSDN【2】寒泉Hq.海量数据处理：如何从10亿个数中，找出最大的10000个数？（topK问题）.CSDN【3】guoziqing506.海量数据处理技巧.CSDN【4】July、youwang、yanxionglu.十道海量数据处理面试题与十个方法大总结.CSDN

深度优先搜索解决矩阵搜索问题

最近在刷LeetCode的时候发现一类和二维矩阵（二维数组）搜索有关的题目，一般使用深度优先或广度优先搜索就可以很好的解决这类题目，这里特意总结一下。1、剑指Offer12.矩阵中的路径这是一个典型的矩阵搜索问题，可使用深度优先搜索（DFS）+剪枝解决。首选，在矩阵中任意选择一个格子作为路径的起点。假设举证中某个格子的字符为ch，并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch,那么这个格子不可能处在路径上的第i个位置。如果路径上第i个字符正好是ch，那么到相邻的格子寻找路径上的第i+1个字符。出矩阵边界上的格子以外，其他格子都有上、下、左、右4个方向可以选择，重复这个过程，知道路径上所有字符都在矩阵中找到相应的位置。并且为了便于控制一个格子只会被访问一遍，我们可以使用一个和矩阵一样大小的boolean矩阵来标识路径是否已经进入了某个格子。相信上面代码一看就会，值得说明的一点使用了isVisited来判断是否再次访问，用来标记已经访问过的点。2、岛屿问题岛屿问题是一类经典的网格搜索类问题。关于岛屿的题目有：200.NumberofIslands岛屿数量695.MaxAreaofIsland岛屿最大面积463.岛屿的周长694.不同岛屿的个数711.不同岛屿的个数II要求解这道题，我们首先来看如何在网格上做DFS如何在网格上做DFS网格问题是这样一类搜索问题：有m\timesnm×n个小方格，组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。这种题目乍一看可能有点麻烦，实际上非常简单，尤其是用DFS的方法。题目没有限制的话，我们尽量用DFS来写代码。下面我们一步步地构造出方格类DFS的代码。首先，每个方格与其上下左右的四个方格相邻，则DFS每次要分出四个岔：但是，对于网格边缘的方格，上下左右并不都有邻居。一种做法是在递归调用之前判断方格的位置，例如位于左边缘，则不访问其左邻居。但这样一个一个判断写起来比较麻烦，我们可以用“先污染后治理”的方法，先做递归调用，再在每个DFS函数的开头判断坐标是否合法，不合法的直接返回。同样地，我们还需要判断该方格是否有岛屿（值是否为1），否则也需要返回。之后为了能够让递归停止下来，我们需要在遍历的时候把已经遍历过的网格做一下标记，可以单独开辟一个和矩阵同样大小的二维boolean矩阵来记录，或者也可以直接修改遍历过的网格的值使其在下一次判断时条件不成立。通常考虑到内存友好，我们直接在原数组上标记就好了。标记遍历过的方格并不需要使用额外的空间，只需要改变方格中存储的值就可以。在这道题中，值为0表示非岛屿（不可遍历），值为1表示岛屿（可遍历），我们用2表示已遍历过的岛屿。这样我们就可以得到网格DFS遍历的框架代码：岛屿有关的二维数组搜索问题，基本都可以在此框架上修改得到结果。我们来看下面几道经典的题。2.1LeetCode200.岛屿数量示例：对于这个二维矩阵进行遍历，如果来到一个是1的位置，开始一个“感染”过程，就是从当前位置出发，把连成一片的1全部变成2。“感染”过程结束之后，继续遍历二维矩阵，直到结束。有多少次“感染”过程，就有多少个岛。实现“感染”过程。假设从i行j列位置出发，向上下左右四个位置依次去“感染”。写成递归函数即可。2.2LeetCode695.岛屿的最大面积示例:基本思路和上面相同，只是需要在遍历每个岛屿的时候，使用一个计数器将这个岛屿的陆地数目记录下来返回，然后比较每个岛屿的大小，返回最大的岛屿的面积即可。代码实现上只需做略微改动即可。2.3LeetCode463.岛屿的周长示例：求岛屿的周长其实有很多种方法，如果用DFS遍历来求的话，有一种很简单的思路：岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。注意，这里的非岛屿方格，既包括水域方格，也包括网格的边界。我们可以画一张图，看得更清晰：将这个“相邻关系”对应到DFS遍历中，就是：每当在DFS遍历中，从一个岛屿方格走向一个非岛屿方格，就将周长加1。完整代码如下：那么每一次进行“深度优先遍历”或者“广度优先遍历”的条件就是：1、这个格子是陆地1，如果是水域0就无从谈论“岛屿”；2、这个格子不能是之前发现“岛屿”的过程中执行了“深度优先遍历”或者“广度优先遍历”操作，而被标记的格子（这句话说得太拗口了，大家意会即可，意会不了不是您的问题，是我表达的问题，直接看代码会清楚很多）。3、剑指Offer13.机器人的运动范围示例：输入：m=2,n=3,k=1输出：3这个题目和前面对题目类似，也可以看做是一个m×n的矩阵。同样，在这个矩阵中，除了边界上的格子，其他位置的格子都有4个相邻的格子。机器人从(0,0)开始。当他准备移动到(i,j)的时候，首先判断他能否进入，如果他可以进入，则在判断它能否进入4个相邻的格子。同时这道题还有一个隐藏的优化：我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。如下图，我们展示了19*19的地图随着限制条件k的放大，可行方格的变化趋势，每个格子里的值为行坐标和列坐标的数位之和，绿色方格代表非障碍方格，即其值小于等于当前的限制条件k。我们可以发现随着限制条件k的增大，(0,0)所在的绿色方格区域内新加入的非障碍方格都可以由上方或左方的格子移动一步得到。而其他不连通的黄色方格区域会随着k的增大而连通，且连通的时候也是由上方或左方的格子移动一步得到，因此我们可以将我们的搜索方向缩减为向右或向下。可以套用岛屿问题中的模板，完整代码如下：参考【1】liweiwei1419.DFS+BFS+并查集（Python代码、Java代码）.力扣（LeetCode）【2】nettee.图解：在DFS遍历过程中求周长（Java）.力扣（LeetCode）

十大经典排序算法（动图演示）

0、算法概述0.1算法分类十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。0.2相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。0.3算法复杂度分析1、冒泡排序（BubbleSort）冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。1.1算法描述比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。1.2动图演示1.3代码实现冒泡排序的优化当我们的数字序列基本有序的时候往往只需要扫描几次就可以排序好了，当数字序列有序了之后在重复扫描那就是在做无用功，因此我们需要优化一下代码的实现。1.4算法分析最好情况下，待排序序列已经有序，只需要进行一次排序，关键字需要n-1次比较，不需要移动记录。最坏情况下，待排序记录刚好是逆序的，此时，每一趟冒泡嘘排序需要n-i次比较，3i次移动。经过n-1趟排序后，总的比较次数为∑(n-i)=n(n-1)/2其中1<=i<=n-1，总的移动次数为3n(n-1)/2次，因此该算法的时间复杂度为O(n^2)，空间复杂度是O(1)。另外它是一种稳定的排序算法。2、选择排序（SelectionSort）选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。2.1算法描述n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。2.2动图演示2.3代码实现2.4算法分析表现最稳定的排序算法之一，因为无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。3、插入排序（InsertionSort）插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。3.1算法描述一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：从第一个元素开始，该元素可以认为已经被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后；重复步骤2~5。3.2动图演示3.2代码实现优化上面的算法在寻找合适的插入位置的时候使用的是顺序查找，非常的耗费时间，既然前面的数字序列是已经排序好的，那么我们可以思考可以用二分查找优化寻找合适插入位置的逻辑。3.4算法分析插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。插入排序在小数据量或数据基本有序的情况下非常高效，但是数据量一大就基本不那么好使了，基于此Shell排序应运而生。4、希尔排序（ShellSort）1959年Shell发明，第一个突破O(n^2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。4.1算法描述先将整个待排序的记录序列分割成为若干子序列（分割成小数据量）分别进行直接插入排序，具体算法描述：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。4.2动图演示4.3代码实现4.4算法分析希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者RobertSedgewick提出的。5、归并排序（MergeSort）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。5.1算法描述把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。5.2动图演示5.3代码实现5.4算法分析归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。6、快速排序（QuickSort）快速排序是对冒泡排序的一种改进,快速排序的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。6.1算法描述快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：从数列中挑出一个元素，称为“基准”（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。6.2动图演示6.3代码实现7、堆排序（HeapSort）堆排序（Heapsort）是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]一般升序排序使用大顶堆，降序排序使用小顶堆。ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：7.1算法描述以升序排序为例，算法思路如下：将待排序的序列构造成一个初始大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素将堆顶根节点元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。7.2动图演示7.3代码实现7.4算法分析堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。8、计数排序（CountingSort）计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。8.1算法描述找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。8.2动图演示8.3代码实现优化8.4算法分析计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。9、桶排序（BucketSort）桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序(Bucketsort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。9.1算法描述设置一个定量的数组当作空桶；遍历输入数据，并且把数据一个一个放到对应的桶里去；对每个不是空的桶进行排序；从不是空的桶里把排好序的数据拼接起来。9.2图片演示9.3代码实现9.4算法分析平均时间复杂度：O(n+k)最佳时间复杂度：O(n+k)最差时间复杂度：O(n^2)空间复杂度：O(n*k)稳定性：稳定10、基数排序（RadixSort）基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。10.1算法描述取得数组中的最大数，并取得位数；arr为原始数组，从最低位开始取每个位组成radix数组；对radix进行计数排序（利用计数排序适用于小范围数的特点）；10.2动图演示10.3代码实现10.4算法分析基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n)，当然d要远远小于n，因此基本上还是线性级别的。基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。参考资料【1】十大经典排序算法（动图演示）【2】图解排序算法(三)之堆排序