递归：如何用三行代码找到“最终推荐人”？
在很多App中，都有推荐注册返佣金这个功能。这个功能中，用户A推荐用户B来注册，用户B又推荐了用户C来注册。于是可以说，用户C的“最终推荐人”为用户A，用户B的“最终推荐人”也为用户A，而用户A没有“最终推荐人”。
一般的话，我们会通过数据库来记录这种推荐关系。在数据库表中，我们可以记录两行数据，其中actor_id表示用户id，referrer_id表示推荐人id。
在这背景下，有一个问题，给定一个用户ID，如何查找这个用户的“最终推荐人”？带着这个问题，来看下面的内容—递归（Recursion）。
一.如何理解递归~~
在数据结构和算法里，可以说有两个最难理解的知识点，一个是动态规划，另一个就是递归。
递归是一种应用非常广泛的算法（或者编程技巧）。很多数据结构和算法的编码实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等。所以，搞懂递归非常重要，否则，一些复杂点的数据结构和算法学起来就会比较吃力。
生活中就有很多用到递归的例子。比如在电影院中想知道坐在第几排，而电影院里又太黑了，看不清，没法数，那该怎么办呢？
这时就可以用递归的方法了。于是，就可以问前面一排的人他是第几排，只要在他的数字上加一，就能找到自己在哪一排了。但，前面的人也看不清啊，所以也问他前面的人，就这样一排一排往前问，直到问到第一排的人，他说他在第一排，再这样一排一排地把数字传回来。直到你前面的人告诉你他在哪一排，你就能知道答案了。
这是一个非常标准的递归求解问题的分解过程，去的过程叫做“递”，回来的过程叫做“归”。基本上，所有的递归问题都可以用递归公式来表示。刚刚这个生活里的例子，用递归公式将它表示出来是这样的：
f(n)=f(n-1)+1其中，f(1)=1
f(n)表示你想知道自己在哪一排，f(n-1)表示前面一排所在的排数，f(1)=1表示第一排的人知道自己在第一排。有了递归公式，可以很轻松地将它改成递归代码，如下：
intf(intn){if(n==1)return1;returnf(n-1)+1;}二.递归满足的三个条件~~
上面这个例子是非常典型的递归，那究竟上面样的问题可以用递归来解决呢？总结地说，只要同时满足以下三个条件，就可以用递归来解决。
一个问题的解可以分解为几个子问题的解
何为子问题？子问题就是数据规模更小的问题。比如，上面的电影院的例子，要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。
这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
比如上面电影院那个例子，求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
存在递归终止条件
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。
还是上面那个电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是f(1)=1，这就是递归的终止条件。
三.如何编写递归代码~~
现在来看一下，如何来写递归代码？个人觉得，写递归代码最关键的是写出递推公式，找到终止条件，剩下就是把递归公式转化为代码了。
先记住这个理论。下面举个例子来加深理解。
假设这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？如果有7个台阶，你可以2，2，2，1这样子上去，也可以1，2，1，1，2这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？
仔细想下，实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了1个台阶，另一类是第一步走了2个台阶。所以，n个台阶的走法就等于先走1阶后，n-1个台阶的走法，加上先走2阶后，n-2个台阶的走法。公式表示如下：
f(n)=f(n-1)+f(n-2)
有了递推公式，递归代码基本上就完成了一半。再来看下终止条件，当有一个台阶时，我们不需要再继续递归，就只有一种走法。所以f(1)=1。这个递归终止条件足够吗？我们可以用n=2，n=3这样比较小的数试验一下。
n=2时，f(2)=f(1)+f(0)。如果递归终止条件只有一个f(1)=1，那f(2)就无法求解了。所以，除了f(1)=1这个递归终止条件外，还要有f(0)=1，表示走0个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了。所以，我们可以把f(2)=2作为一种终止条件，表示走2个台阶，有两种走法，一步走完或者分两步来走。
所以，递归终止条件就是f(1)=1，f(2)=2。这时候，可以拿n=3，n=4来验证一下，这个终止条件是否足够并且正确。
把递归终止条件和刚刚得到的递推公式放到一起后如下：
f(1)=1;f(2)=2;f(n)=f(n-1)+f(n-2)
有了这个公式，转化成递归代码就简单多了。最终的递归代码是这样的：
intf(intn){if(n==1)return1;if(n==2)return2;returnf(n-1)+f(n-2);}总结一下，写递归代码的关键就是找到如何把大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
而刚讲的电影院的例子，递归调用只有一个分支，也就是“一个问题只需要分解为一个子问题”，很容易能够想取出“递”和“归”的每一个步骤，所以写起来，理解起来都不难。
但是，当我们面对的是一个问题要分解为多个子问题的情况，递归代码就没那么好理解了。
像刚刚那个走台阶的例子，人脑几乎没办法把整个“递”和“归”的过程一步一步想清楚。
计算机擅长做重复的事情，所以递归正合它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去。
对于递归代码，这种试图想清楚整个递和归过程的做法，实际上是进入了一种思维误区。很多时候，我们理解起来比较吃力，主要原因是自己给自己制造了这种理解障碍。那正确的思维方式是怎样的呢？
如果一个问题A可以分解为若干个子问题B、C、D，可以假设B、C、D已经解决，在此基础上思考如何解决问题A。而且，只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。
因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。
四.递归代码要警惕堆栈溢出~~
在实际的软件开发中，编写递归代码时，我们会遇到很多问题，比如堆栈溢出。而堆栈溢出会造成系统性崩溃，后果会非常严重。为什么递归代码容易造成堆栈溢出呢？我们又该如何预防堆栈溢出呢？
之前在栈那里说过，函数调用会使用栈来保存临时变量，每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。
比如上面讲到的电影院的例子，如果我们将系统栈或者JVM堆栈大小设置为1KB，在求解f()时便会出现如下堆栈报错：
Exceptioninthread"main"java.lang.StackOverflowError那么，如何避免出现堆栈溢出呢？
我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题，递归调用超过一定深度（比如）之后，我们就不继续往下递归了，直接返回报错。还是电影院那个例子，改造成下面这样子，就可以避免堆栈溢出了。不过，这里的代码是伪代码，为了代码简洁，有些边界条件没有考虑，比如x=0。
//全局变量，表示递归的深度。intdepth=0;intf(intn){++depth；if(depth)throwexception;if(n==1)return1;returnf(n-1)+1;}但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。而如果实时计算，会使代码过于复杂，影响代码的可读性。所以，如果最大深度比较小，比如10、50，就可以用这种方法，否则此方法并不是很实用。
五.递归代码要警惕重复计算~~
使用递归还会出现重复计算的问题。比如刚刚走台阶的那个例子，如果把整个递归过程分解一下的话，则如下图所示：
从图中可以直观地看到，想要计算f(5)，需要先计算f(4)和f(3)，而计算f(4)还需要计算f(3)，因此，f(3)就被计算了很多次，这就是重复计算问题。
为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的f(k)。当递归调用到f(k)时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免重复计算了。
按照这个思路，改造一下刚刚的代码如下：
publicintf(intn){if(n==1)return1;if(n==2)return2;//hasSolvedList可以理解成一个Map，key是n，value是f(n)if(hasSolvedList.containsKey(n)){returnhasSolvedList.get(n);}intret=f(n-1)+f(n-2);hasSolvedList.put(n,ret);returnret;}除了堆栈溢出、重复计算这两个常见的问题，递归代码还有很多别的问题。
在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销，比如上面的电影院递归代码，空间复杂度并不是O(1)而是O(n)。
六.怎么将递归代码改写为非递归代码？
递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，要根据实际情况来选择是否需要用递归的方式来实现。
那我们是否可以把递归代码改写为非递归代码呢？比如上面那个电影院的例子，抛开场景，只看f(x)=f(x-1)+1这个递推公式。可以这样改写：
intf(intn){intret=1;for(inti=2;i=n;++i){ret=ret+1;}returnret;}同样，走台阶的例子也可以改为非递归的实现方式：
intf(intn){if(n==1)return1;if(n==2)return2;intret=0;intpre=2;intprepre=1;for(inti=3;i=n;++i){ret=pre+prepre;prepre=pre;pre=ret;}returnret;}那是不是所有的递归代码都可以改为这种迭代循环的非递归写法呢？
笼统地讲，是的。因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。
但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决上面讲到的某些问题，徒增了实现的复杂度。
七.如何找到“最终推荐人”？
解决方案是这样的：
longfindRootReferrerId(longactorId){LongreferrerId=selectreferrer_idfrom[table]whereactor_id=actorId;if(referrerId==null)returnactorId;returnfindRootReferrerId(referrerId);}是不是非常简洁？用三行代码就能搞定了，
不过在实际项目中，这个代码并不能工作，为什么呢？有两个问题：
第一，如果递归很深，可能会有堆栈溢出的问题。这个问题用限制递归深度就能解决了。
第二，如果数据库里存在脏数据，还需要处理由此产生的无限递归问题。比如demo环境下数据库中，测试工程师为了方便测试，会人为地插入一些数据，就会出现脏数据。如果A的推荐人是B，B的推荐人是C，C的推荐人是A，这样就会发生死循环。这个问题也可以用限制递归深度来解决。不过，还有一个更高级的处理方法，就是自动检测A-B-C-A这种“环”的存在。
1.平时调试代码喜欢使用IDE的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？
调试递归的方法有：
打印日志发现，递归值，简单的解释就是输出，每次递归的时候增加printf()；
结合条件断点进行调试，更确切的说法是“结合条件语句进行断点调试”，也就是给断点加上条件，符合条件才进入断点；
2.限制递归深度的做法只适合规模比较小的情况，那如果规模大的话，如何限制呢？
可以自己模拟一个栈，用非递归代码来实现。
3.如何检测一个A-B-C-A这种“环”的存在？
可以构造一个SET集合或者散列表。每次获取到上层推荐人就去散列表里先查，没有查到的话就加入，如果存在则表示存在环了。
4.递归实际上和数学归纳法非常像，所以可以利用数学归纳法的思路，先验证边界条件，再假设n-1的情况正确，思考n和n-1的关系写出递推公式。
5.递的过程=函数持续求解的过程=入栈，
归的过程=return持续返回的过程=出栈
6.走台阶的过程其实就是斐波那契数列。
7.实际上，堆和栈的第一个区别就是申请方式不同；栈（Stack）是系统自动分配空间的，例如我们定义一个chara；系统会自动在栈上为其开辟空间，而堆（heap）则是程序员根据需要自己申请的空间，例如malloc(10)；开辟十个字节的空间。由于栈上的空间是自动分配自动回收的，所以栈上数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。Windows下，栈是向低地址扩展的数据结构，是一块连续的内存区域。也就是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有的说法是1M，总之是一个编译时就能确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
8.递归是自上而下的解决问题，非递归是自下而上的解决问题。
排序（上）：为什么插入排序比冒泡排序更受欢迎？
排序对于任何一个程序员来说，可能都不会陌生。学的第一个算法，可能就是排序。大部分编程语言中，也都提供了排序函数。在平常的项目中，我们也经常会用到排序。所以要多花一点时间来看看经典的排序算法。
排序算法太多了，有很多可能连名字都没听过，比如猴子排序、睡眠排序、面条排序等。咱们只看众多排序算法中的一小撮，最经典、最常用的：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。根据时间复杂度，它们可以分成三类。
我们先看一下冒泡排序、插入排序和选择排序。还是先来思考一个问题：插入排序和冒泡排序的时间复杂度相同，都是O(n^2)，那为什么在实际的软件开发里，我们更倾向于使用插入排序算法而不是冒泡排序算法呢？
一.如何分析一个“排序算法”？
学习排序算法，除了学习它的算法原理、代码实现之外，更重要的是学会如何评价、分析一个排序算法。分析一个排序算法，可以从下面几方面入手：
排序算法的执行效率
对于算法执行效率的分析，一般会从如下几方面来衡量：
最好情况、最坏情况、平均时间复杂度
在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，还要给出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。
为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序，有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。
时间复杂度的系数、常数、低阶
我们知道，时间复杂度反映的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是10个、个、个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们要把系数、常数、低阶也考虑进来。
比较次数和交换次数
这里的都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，我们在分析排序算法的执行效率时候，应该把比较次数和交换（或移动）次数也考虑进去。
排序算法的内存消耗
之前说过，算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，还引入了一个新的概念，原地排序（Sortedinplace）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。下面的冒泡、插入、选择排序都是原地排序算法。
排序算法的稳定性
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，我们还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序是不变的。
用一个例子来解释一下，比如有一组数据2，9，3，4，8，3，按照大小排序之后就是2，3，3，4，8，9。
这组数据里有两个3。经过某种排序算法排序之后，如果两个3的前后顺序没有改变，那我们就把这种排序算法叫做稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫做不稳定的排序算法。
为什么要考察排序算法的稳定性呢？
那是因为，虽然很多数据结构和算法课程，在将排序的时候，都是用整数来举例，但在实际的软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个key来排序。
比如，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果有10万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，怎么做呢？
最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
而借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：我们先按照下单时间给订单排序，注意是按照下单时间，不是金额。排序完成之后，用稳定排序算法，按照订单金额重新排序。两遍排序之后，我们得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的，为什么呢？
因为，稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。第一次排序之后，所有的订单按照下单时间从早到晚有序了。而在第二次排序中，我们用的是稳定排序算法，所以经过第二次排序之后，相同金额的订单仍然保持下单时间从早到晚有序。
二.冒泡排序（BubbleSort）~~
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系。如果不满足就让它两互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
举个例子，看下冒泡排序的过程。我们对一组数据4，5，6，3，2，1，从小到大进行排序。第一次冒泡操作的详细过程如下：
可以看到，经过一次冒泡操作之后，6这个数据会“冒到”正确的位置上。要想完成所有数据的排序，我们只要进行6次这样的冒泡操作就行了。
实际上，刚才的冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不需要再继续执行后续的冒泡操作。这里还有另外一个例子如下，给6个元素排序，只需要4次冒泡操作就可以了。
冒泡排序算法的原理比较容易理解，具体代码如下：
//冒泡排序，a表示数组，n表示数组大小publicvoidbubbleSort(int[]a,intn){if(n=1)return;for(inti=0;in;++i){//提前退出冒泡循环的标志位booleanflag=false;for(intj=0;jn-i-1;++j){if(a[j]a[j+1]){//交换inttmp=a[j];a[j]=a[j+1];a[j+1]=tmp;flag=true;//表示有数据交换}}if(!flag)break;//没有数据交换，提前退出}//当且仅当该交换的都交换完了才能break}现在，结合刚才分析排序算法的三个方面，有三个问题。
冒泡排序是原地排序算法吗
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。
冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，这次冒泡操作因为没有数据交换而退出了，所以最好情况时间复杂度是O(n)。而最坏情况是，要排序的数据刚好是倒序排列的，我们需要进行n次冒泡操作，一次把一个数据冒到它正确存储的位置上。所以最坏情况时间复杂度为O(n^2)。
最好、最坏情况下的时间复杂度很容易分析，那平均情况下的时间复杂度是多少？之前说过，平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。
对于包含n个数据的数组，这n个数据就有n！种排列方式。不同的排列方式，冒泡排序执行的时间肯定是不同的。比如上面那两个例子，一个要6次冒泡，而另一个只要4次。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。这里还有一种思路，通过“有序度”和“逆序度”这两个概念来进行分析。
有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示如下：
有序元素对：a=a[j],如果ij。
同理，对于一个倒序排列的数组，比如6，5，4，3，2，1，有序度是0；对于一个完全有序的数组，比如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15。我们把这种完全有序的数组的有序度叫做满有序度。
逆序度的定义正好跟有序度相反（默认从小到大为有序），逆序度的定义如下：
逆序元素对：aa[j],如果ij。关于这三个概念，可以得到一个公式：逆有序度=满有序度-有序度。排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。
还是拿上面那个冒泡排序的例子来说明。要排序的数组的初始状态是4，5，6，3，2，1，其中，有序元素对有（4，5）（4，6）（5，6），所以有序度是3。n=6，排序完成之后最终状态的满有序度为n*(n-1)/2=15。
冒泡操作包含两个操作原子，比较和交换，每交换一次，有序度就加1。不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2-初始有序度。此例中就是15-3=12，要进行12次交换操作。
对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是0，要进行n*(n-1)/2，就不需要进行交换。可以取个中间值n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。
换句话说，平均情况下，需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是O(n^2)，所以平均情况下的时间复杂度就是O(n^2)。
虽然这个平均时间复杂度推导过程并不严格，但很多时候很实用。
三.插入排序（InsertionSort）~~
先来看一个问题。一个有序的数组，往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，只需要遍历数组，找到数据应该插入的位置将其插入即可。
这是一个动态排序的过程，即动态地往有序集合中添加数据，可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据，可以借鉴这种插入方法，来进行排序，于是就有了插入排序算法。
那插入排序具体是如何借助这种思想来实现排序的呢？
首先，将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入。并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
如图所示，要排序的数据是4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。
插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，还需要将插入点后的元素顺序往后移动一位，这样才能腾出位置给元素a插入。
对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。
为什么说移动次数就等于逆序度呢？拿刚刚的例子画个图表如下。满有序度是n*(n-1)/2=15，初始序列的有序度是5，所以逆序度是10。插入排序中，数据移动的个数总和也等于10=3+3+4。
下面是插入排序的代码实现：
//插入排序，a表示数组，n表示数组大小，j代表已排序区间，//for循环里当且仅当新的未排序的这一位小于已排序区间里的某一个才挪位置//里面的for循环挪完位置后就break，break后的j就是要放进去的//也有直接不挪的，放在原位的publicvoidinsertionSort(int[]a,intn){if(n=1)return;for(inti=1;in;++i){intvalue=a;intj=i-1;//查找插入的位置for(;j=0;--j){//这里j的区间=0代表已排序的从0到j的位置if(a[j]value){//--j的操作是为了遍历，a[j+1]=a[j];//数据移动}else{//当已排序区间该挪动的都挪动后，会再来一次--jbreak;}}a[j+1]=value;//插入数据,这里j+1是为了补充上面那次跳出多减的一次}}这里还是有三个问题：
插入排序是原地排序算法吗
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。
插入排序是稳定的排序算法吗
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入顺序是稳定的排序算法。
插入排序的时间复杂度是多少
如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。从第二位开始，每次与左边的有序区间比较一次即可判断出不需要移动，所以总的次数n-1，O(n)。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，也就是最坏情况时间复杂度为O(n^2)。插入排序要判断n轮，完全倒序会使得后面所有元素都要遍历后移n次。
而在数组中插入一个数据的平均时间复杂度是O(n)。因为涉及到数据的搬移。所以，对于插入排序来说，每次插入查找都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n^2)。
四.选择排序（SelectionSort）~
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次都会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
代码如下：
//选择排序，a表示数组，n表示数组大小publicstaticvoidselectionSort(int[]a,intn){if(n=1)return;for(inti=0;in-1;++i){//查找最小值intminIndex=i;for(intj=i+1;jn;++j){if(a[j]a[minIndex]){minIndex=j;}}//交换inttmp=a;a=a[minIndex];a[minIndex]=tmp;}}同样，这里也有和前面一样的三个问题，答案如下：
首先，选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n^2)。因为不管原来的顺序是什么，都要从无序数组中找到最小值，而最小值只能通过全部比较一次才能得到，然后做交换。
那选择排序是稳定的排序算法吗？
答案是否定的，选择排序是一种不稳定的排序算法。从上面那张图中，可以看到，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如5，8，5，2，9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个元素5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。
五.为什么插入排序要比冒泡排序更受欢迎呢？
虽然冒泡排序和插入排序的时间复杂度都是O(n^2)，都是原地排序算法，但之前分析的时候说到，冒泡排序和插入排序是一样的，不管怎么优化，元素移动的次数都等于原始数据的逆序度。
但是，从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，如下：
冒泡排序中数据的交换操作：if(a[j]a[j+1]){//交换，一个一个冒出去inttmp=a[j];a[j]=a[j+1];a[j+1]=tmp;flag=true;}插入排序中数据的移动操作：if(a[j]value){a[j+1]=a[j];//数据移动，没有临时变量去暂存，一个一个腾位置}else{break;}我们把执行一个赋值语句的时间粗略地记为单位时间（unit_time），然后分别用冒泡和插入排序对同一个逆序度是K的数组进行排序。这里是以逆序度为基准，用冒泡排序，需要K次交换操作，每次需要3个赋值语句，所以交换操作耗时就是3*K单位时间。而插入排序中数据移动操作只需要K个单位时间。
当然这只是非常理论的分析。实验一下，针对上面的冒泡排序和插入排序的Java代码，写一个性能对比测试程序，随机生成0个数组，每个数组中包含个数据，在机器上用冒泡和插入排序算法来排序，冒泡排序算法大约ms才能执行完成，而插入排序只需要ms左右就能搞定。
所以，虽然冒泡排序和插入排序在时间复杂度上都是O(n^2)，但如果要把性能优化做到极致，肯定首选排序。
1.之前说过，特定算法都是依赖特定的数据结构的。如果上面三种排序算法不是基于数组实现的，而是存储在链表中，三种排序算法还能工作吗？如果能，对应的时间、空间复杂度又是多少？
三种排序算法不涉及随机读取，所以链表是可以实现的，而且时间复杂度空间复杂度和数组一样。
但这个问题应该要有一个前提，是否允许修改链表的结点value值，还是只能改变结点的位置。一般而言，考虑只能改变结点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。
2.插入和冒泡排序虽然时间复杂度都是O(n^2)，但是插入排序的比较次数比冒泡少，因为插入排序左侧是已经排序好的了。还有一个点是冒泡需要全部比较完，插入比较到正确位置就可以了。而插入排序的intvalue=a，类似于链表里说到的哨兵思想，通过哨兵降低时间复杂度，对于大量数据效率有很大提升。
排序：如何用快排思想在O(n)内查找第K大元素？
上面的冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是O(n^2)，比较高，适合小规模数据的排序，下面是两种时间复杂度为O(nlogn)的排序算法，归并排序和快速排序。这两种排序算法适合大规模的数据排序，比上面那三种排序算法要更常用。
归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如：如何在O(n)的时间复杂度内查找一个无序数组中的第K大元素？
一.归并排序（MergeSort）的原理~
归并排序的核心思想还是蛮简单的，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
这描述，觉不觉得和前面的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，这两者并不冲突。
归并排序用的是分治思想，可以用递归来实现。现在就看看如何用递归代码来实现归并排序。
之前说过，递归代码的编写技巧就是分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。归并排序也是一样的。
递推公式：merge_sort(p…r)=merge(merge_sort(p…q),merge_sort(q+1…r))终止条件：p=r不用再继续分解来解释一下这个递推公式：
merge_sort(p..r)表示，给下标从p到r之间的数组排序。我们将这个排序问题转化成了两个子问题，merge_sort(p..q)和merge_sort(q+1..r)，其中下标q等于p和r的中间位置，也就是(p+r)/2。当下标从p到q和从q+1到r这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从p到r之间的数据也就排好序了。
有了递推公式，转化成代码就简单多了。下面是归并排序的伪代码。
//归并排序算法,A是数组，n表示数组大小merge_sort(A,n){merge_sort_c(A,0,n-1)}//递归调用函数merge_sort_c(A,p,r){//递归终止条件ifp=rthenreturn//最后数据区间变成的时候排序就完成了//取p到r之间的中间位置qq=(p+r)/2//分治递归merge_sort_c(A,p,q)merge_sort_c(A,q+1,r)//将A[p...q]和A[q+1...r]合并为A[p...r]merge(A[p...r],A[p...q],A[q+1...r])}你可能已经发现了，merge(A[p...r],A[p...q],A[q+1...r])这个函数的作用就是，将已经有序的A[p...q]和A[q+1...r]合并成一个有序的数组，并且放入A[p...r]。这个过程具体如何做呢？
如图所示，我们申请一个临时数组tmp，大小与A[p...r]相同。我们用两个游标i和j，分别指向A[p...q]和A[q+1...r]的第一个元素。比较这两个元素A和A[j]，如果A=A[j]，我们把A放入到临时数组tmp，并且i后移一位，否则将A[j]放入到数组tmp，j后移一位。
继续上述比较过程，直到其中一个子数组中的所有数据都放入到临时数组中，再把另一个数组中的数据依次加入到临时数组的末尾，这个时候，临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组tmp中的数据拷贝到原数组A[p...r]中。
把merge()函数写成伪代码，如下：
merge(A[p...r],A[p...q],A[q+1...r]){vari:=p，j:=q+1，k:=0//初始化变量i,j,kvartmp:=newarray[0...r-p]//申请一个大小跟A[p...r]一样的临时数组whilei=qANDj=rdo{ifA=A[j]{tmp[k++]=A[i++]//i++等于i:=i+1}else{tmp[k++]=A[j++]}}//判断哪个子数组中有剩余的数据varstart:=i，end:=qifj=rthenstart:=j,end:=r//将剩余的数据拷贝到临时数组tmpwhilestart=enddo{tmp[k++]=A[start++]}//将tmp中的数组拷贝回A[p...r]fori:=0tor-pdo{A[p+i]=tmp}}其实merge()合并函数如果借助哨兵，代码就会简洁很多。代码如下：
privatestaticvoidmergeBySentry(int[]arr,intp,intq,intr){int[]leftArr=newint[q-p+2];int[]rightArr=newint[r-q+1];for(inti=0;i=q-p;i++){leftArr=arr[p+i];}//第一个数组添加哨兵（最大值）leftArr[q-p+1]=Integer.MAX_VALUE;for(inti=0;ir-q;i++){rightArr=arr[q+1+i];}//第二个数组添加哨兵（最大值）rightArr[r-q]=Integer.MAX_VALUE;inti=0;intj=0;intk=p;while(k=r){//当左边数组到达哨兵值时，i不再增加，直到右边数组读取完剩余值，同理右边数组也一样if(leftArr=rightArr[j]){arr[k++]=leftArr[i++];}else{arr[k++]=rightArr[j++];}}}二.归并排序的性能分析~
接着还是分析排序算法的那三个问题：
归并排序是稳定的排序算法吗？
结合上面画的那张图和归并排序的伪代码，应该能发现，归并排序稳不稳定关键要看merge()函数，也就是把两个有序子数组合并成一个有序数组的那部分代码。毕竟归并排序是分而治之，分裂成无数的小数组。
在合并过程中，如果A[p...q]和A[q+1...r]之间有值相同的元素，我们可以像伪代码那样，先把A[p...q]中的元素放入tmp数组。这样就保持了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
归并排序的时间复杂度是多少？
归并排序涉及递归，时间复杂度发分析稍微复杂了点。如何分析呢？
之前递归那说过，递归的适用场景是，一个问题a可以分解为多个子问题b，c，那求解问题a就可以分解成求解问题b，c。问题b、c解决之后，我们再把b、c的结果合并成a的结果。
所以，如果我们定义求解问题a的时间是T(a)，求解问题b、c的时间分别是T(b)和T(c)，那我们就可以得到这样的递推关系式：
T(a)=T(b)+T(c)+K其中K等于将两个子问题b、c的结果合并成问题a的结果所消耗的时间。
从这个分析，可以得到一个重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
套用这个公式，来分析一下归并排序。
我们假设对n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的时间都是T(n/2)。而由上面的分析可以知道，merge()函数合并两个有序子数组的时间复杂度的时间复杂度是O(n)。所以，套用上面的公式，归并排序的时间复杂度的计算公式就是：
T(1)=C；n=1时，只需要常量级的执行时间，所以表示为C。T(n)=2*T(n/2)+n；n1
通过这个公式，如何求解T(n)呢？分解后如下
T(n)=2*T(n/2)+n=2*(2*T(n/4)+n/2)+n=4*T(n/4)+2*n=4*(2*T(n/8)+n/4)+2*n=8*T(n/8)+3*n=8*(2*T(n/16)+n/8)+3*n=16*T(n/16)+4*n......=2^k*T(n/2^k)+k*n......
这不断分解，分解到T(1)实际上也是归并排序的求解过程。通过这样一步一步分解推导，可以得到T(n)=2^k*T(n/2^k)+k*n。当T(n/2^k)=T(1)时，也就是n/2^k=1时，我们得到k=log2n。我们将k值代入公式，得到T(n)=Cn+nlog2n。如果用大O表示法来表示，T(n)就等于O(logn)。所以归并排序的时间复杂度是O(logn)。
而从原理分析和伪代码可以看出，归并排序的执行效率和要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好、最坏还是平均情况，时间复杂度都是O(logn)。
归并排序的空间复杂度是多少？
虽然归并排序的时间复杂度看起来非常优秀，但它有一个致命的“弱点”，不是原地排序算法。
因为归并排序的合并函数，合并时需要借助额外的存储空间。那归并排序的空间复杂度到底是多少呢？
如果继续按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是O(nlogn)。
但这个思路是不对的。递归代码的空间复杂度并不能像时间复杂度那样累加。因为，实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只有一个临时的内存空间在使用。临时内存空间最大也不会超过n个数据的大小，所以空间复杂度是O(n)。
三.快速排序的原理~
我们再来看快速排序算法（Quicksort），习惯简称为“快排”。快排利用的也是分治思想。快排利用的也是分治思想。乍一看，它有点像归并排序，但是思路完全不一样。先来看快排的核心思想。
快排的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，我们选择p到r之间的任意一个数据作为pivot（分区点）。
我们遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。
根据分治、递归的处理思想，我们可以用递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。
如果我们用递归公式来将上面的过程写出来的话，就是这样：
递推公式：quick_sort(p…r)=quick_sort(p…q-1)+quick_sort(q+1…r)先递归将数组的整个区间分成一个一个的子区间，也就是每个单独的数，划分好后由merge合并终止条件：p=r把递归公式转化成递归代码，用伪代码来实现，如下：
//快速排序，A是数组，n表示数组的大小quick_sort(A,n){quick_sort_c(A,0,n-1)}//快速排序递归函数，p,r为下标quick_sort_c(A,p,r){ifp=rthenreturn//显然当pr时有一直分解下去q=partition(A,p,r)//获取分区点quick_sort_c(A,p,q-1)quick_sort_c(A,q+1,r)}归并排序中有一个merge()合并函数，而这里有一个partition()分区函数。partition()分区函数实际上就是前面讲过的，随机选择一个元素作为pivot（一般情况下，可以选择p到r区间的最后一个元素），然后对A[p...r]分区，函数返回pivot的下标。
如果不考虑空间消耗的话，partition()分区函数可以写得非常简单。我们申请两个临时数组X和Y，遍历A[p...r]，将小于pivot的元素都拷贝到临时数组X，将大于pivot的元素都拷贝到临时数组Y，最后再将数组X和数组Y中的数据顺序拷贝到A[p...r]。
但是，如果按照这种思路实现的话，partition()函数就需要很多额外的内存空间，就使得快排不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度得是O(1)，那partition()分区函数就不能占用太多额外的内存空间，就需要在A[p...r]的原地完成分区操作。
原地排序函数的实现思路非常巧妙，伪代码如下：
partition(A,p,r){pivot:=A[r]i:=pforj:=ptor-1do{ifA[j]pivot{swapAwithA[j]i:=i+1}}swapAwithA[r]returni这里的处理有点类似选择排序，我们通过游标i把A[p...r-1]分成两部分。A[p...i-1]的元素都是小于pivot的，我们暂且叫它“已处理区间”，A[i...r-1]是“未处理区间”。我们每次都从未处理的区间A[i...r-1]中取一个元素A[j]，与pivot对比，如果小于pivot，则将其加入到已处理区间的尾部，也就是A的位置。这里可以这么理解，用j去扫描A[p..r]除了pivot的所有元素，一旦扫到有一个小于pivot的元素，就把它放到i的位置上，然后让i+1，而i的起始位置是p，这些条件可以保证，当j走到r-1时，此时i的位置就是pivot应有的位置。
而这里用到了一个有趣的操作，也就是数组插入操作的优化。原本在数组某个位置插入元素，需要搬移数据，非常耗时。而使用这种交换的处理技巧来优化，能使得在O(1)的时间复杂度内完成插入操作。也就是只需要将A与A[j]交换，就可以在O(1)时间复杂度内将A[j]放到下标为i的位置。
如下图所示，是分区的整个过程：
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个6的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
现在再来看另外一个问题：快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并，可以说先让子数组有序，再让它合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。这里可以说先把一个pivot放到它合适的位置上，接着再对分区后的两侧进行处理。
归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法，但它是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
四.快速排序的性能分析~
现在来分析一下快排的性能。上面已经说了快排的稳定性和空间复杂度。快排是一种不稳定、原地的排序算法。现在，我们来看一下快排的时间复杂度。
快排也是用递归来实现的。对于递归代码的时间复杂度，上面总结的公式，这里也是适用的。如果每次分区操作，都能正好把数组分成大小接近的两个小区间，那快排的时间复杂度递推求解公式跟归并也是相同的，此时快排的时间复杂度也是O(nlogn)。
T(1)=C；n=1时，只需要常量级的执行时间，所以表示为C。T(n)=2*T(n/2)+n；n1
但是，公式成立的前提是每次分区操作，选择的pivot都很合适，都正好能将大区间对等地一分为二。但这种情况实际上是很难实现的。
举一个比较极端的例子。如果数组中的数据原来已经是有序的，比如1，3，5，6，8。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间都是不均等的。分区操作的时间复杂度都是O(n)。我们需要进行大约n次分区操作，才能完成整个快排的整个过程，每次分区我们平均要扫描大约n/2个元素，第一次要扫n-1个，最后一次扫1个。这种情况下，快排的时间复杂度就从O(nlogn)退化成了O(n^2)。
上面这两种是极端情况下的时间复杂度。一个分区极其均衡，一个是分区极其不均衡。分别对应着最好情况时间复杂度和最坏情况时间复杂度。那快排的平均情况复杂度是多少呢？
假设每次分区都将区间分成大小为9：1的两个小区间。继续套用递归时间复杂度的递推公式，会变成这样：
T(1)=C；n=1时，只需要常量级的执行时间，所以表示为C。T(n)=T(n/10)+T(9*n/10)+n；n1
但这个公式的递推求解非常复杂，虽然可以求解，但不推荐用这种方法。实际上，递归的时间复杂度求解方法除了递推公式之外，还有递归树。这里先直接给结论：T(n)在大部分情况下的时间复杂度都可以做到O(nlogn)，只有在极端情况下，才会退化到O(n^2)，而这个概率非常小。我们可以通过合理地选择pivot来避免这种情况。
五.如何在O(n)时间复杂度内求无序数组中的第K大元素
快排核心思想就是分治和分区。可以利用分区的思想，来解决这个问题，比如，4，2，5，12，3这样一个无序数组，第3大元素就是4。
我们选择数组区间A[0...n-1]的最后一个元素A[n-1]作为pivot，对数组A[0...n-1]原地分区，这样数组就分成了三部分，A[0...p-1]、A[p]、A[p+1...n-1]。
如果p+1=K，那A[p]就是要求解的元素，因为数组计数从0开始；如果Kp+1，说明第K大元素出现在A[p+1...n-1]区间，所以再按照说明的思路递归地在这个区间内查找。同理，如果Kp+1，就在A[0...p-1]区间查找。
那为什么这种解决思路的时间复杂度是O(n)?
快排这种排序做法在大部分情况下时间复杂度都能做到O(nlogn)，只有极端情况下才会退化成O(n^2)。
也就意味着，第一次分区查找，我们需要对大小为n的数组执行分区操作，需要遍历n个元素。第二次分区查找，我们只需要对大小为n/2的数组执行分区操作，需要遍历n/2个元素。依次类推，分区遍历元素的个数分别为n/2、n/4、n/8、n/16.....直到区间缩小为1。
如果我们把每次分区遍历的元素个数加起来，就是：n+n/2+n/4+n/8+...+1。这是一个等比数列求和。最后的和等于2n-1。所以，这个解决思路的时间复杂度就为O(n)。
你可能会说，用很笨的办法，每次取数组中的最小值，将其移动到数组的最前面，然后在剩下的数组中继续找最小值，以此类推，执行K次，找到的数据不就是第K大元素了？
但这种做法的时间复杂度就不是O(n)，而是O(K*n)。因为当K是比较小的常量时，比如1、2，那最好时间复杂度确实是O(n)；但当K等于n/2或者n时，这种最坏情况下的时间复杂度就是O(n^2)了。
1.如果现在你有10个接口访问日志文件，每个日志文件大小约MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB，有什么好的解决思路，能“快速”地将这10个日志文件合并？
先构建十条IO流，分别指向十个文件，每条IO流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的IO流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，IO流读取下一行数据，以此类推，完成文件的合并。这种处理方式，日志文件里有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O(n)，空间复杂度是O(1)，几乎不占用内存。
显然这是归并的思路。
这想法不错，但实操的时候应该要考虑利用内存来降低读写文件的IO消耗，例如写的时候利用一部分内存来缓存一部分写入，达到瓶颈后一次性batch写入。读的时候可以一次性多读一些。IO流不占内存，它只是提供读写操作，可以把它想象成一个移动的指针，而且可以使用工具类逐条读。当然也可以开辟一块内存区域保存一条一条排序的结果，等临时内存快满了，再刷到文件里面，一条一条写起来会很慢。
但每次只读取一条数据，磁盘I/O会是瓶颈，可以考虑利用内存，比如一次批量读入一批日志到内存，比如维护一个数组，然后在内存中对着10个数组流进行取一条-快排得到最小值-顺序取下一条，这样实际时间应该会快不少。
另外一种思路是先取得十个文件时间戳的最小值数组的最小值a，和最大值数组的最大值b。然后取mid=(a+b)/2，然后把每个文件按照mid分割，取所有前面部分之和，如果小于1G就可以读入内存快排生成中间文件，否则继续取时间戳的中间值分割文件，直到区间内文件之和小于1G。同理对所有区间都做相同处理。最终把生成的中间文件按照分割的时间区间的次序直接连起来就行。也就充分利用每个文件记录的有序性，也充分利用了内存。这是快排的思路。
第三种方法是申请10个40M的数组和一个M的数组；每个文件都读40M，取各数组中最大时间戳中的最小值，这是第二步；然后利用二分查找，在其他数组中快速得到=该时间戳的位置，并做标记；再把各数组中标记位置之前的数据全部放在申请的M内存中；在原来的40M数组中清除已参加排序的数据[可以优化成不挪动数据，只是用两个索引标记有效数据的起始位置和截止位置]；对M内存中的有效数据[没装满]做快排。将排好序的直接写文件；再把每个数组尽量填充满，从第二步开始继续，直到各个文件都读取完毕。
这么做的好处如下：
批量读取，比每次只取一条快多了；充分利用了读取到内存的数据，上面那个在文件中查找中间数是比较困难的。每个拷贝到M大数组参加快排的数据都被写到了文件中，这样每个数都只参加了一次快排。
2.快排是在拆分时排序，归并是在合并时排序。
线性排序：如何根据年龄给万用户数据排序？
下面将介绍三种时间复杂度为O(n)的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们也把这类排序算法叫做线性排序（Linearsort）。而之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
这几种排序算法理解起来都不难，时间、空间复杂度分析也很简单，但对要排序的数据要求很苛刻，故学习的重点是掌握这些排序算法的适用场景。
老样子，还是先给一道思考题：如何根据年龄给万用户排序，你可能想，用上面的归并、快排也可以搞定啊！它们确实可以完成功能，但是时间复杂度最低也是O(nlogn)。有没有更快的排序方法呢，就是下面的内容了。
一.桶排序（Bucketsort）
先来看桶排序。桶排序，顾名思义，会用到“桶”。核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序的时间复杂度为什么是O(n)呢？一起来分析一下。
如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。对每个桶内部使用快速排序，时间复杂度为O(k*logk)。m个桶排序的时间复杂度就是O(m*k*logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n*log(n/m))。当桶的个数m接近数据个数n时，log(n/m)就是一个非常小的常量，这个时候桶排序的时间复杂度就接近O(n)。
看起来很优秀，那它是不是可以替代之前的排序算法呢？
答案是否定的。从上面桶排序的核心思想可以看出，里面有很多假设。实际上，桶排序对于要排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分成m个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排完序之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不均匀，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为O(nlogn)的排序算法了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说有10GB的订单数据，我们希望按照订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百MB，没办法一次性把10GB的数据都加载到内存中。
这时候可以借助桶排序的处理思想来解决这个问题。
可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后得到，订单金额最小是1元，最大是10万元。我们将所有订单根据金额划分到个桶里，第一个桶里我们存储金额在1元到元之内的订单，第二个桶存储金额在1元到0元之间的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02...99）。
理想情况下，如果订单金额在1到10万之间均匀分布，那订单会被均匀划分到个文件中，每个小文件中存储大约MB的订单数据，我们就可以将这个小文件依次放到内存中，用快排来排序。等所有文件都排好序后，我们只需要按照文件编号，从小到大依次读取每个小文件的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
不过，订单按照金额在1元到10万元之间并不一定是均匀分布的，所以10GB订单数据是无法均匀地被划分到个文件中的。有可能某个金额区间的数据特别地多，划分之后对应的文件就会很大，没法一次性读入内存。该这么办呢？
针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在1元到元之间的比较多，我们就将这个区间继续划分为10个小区间，1元到元，元到元，元到元...元到元。如果划分之后，元到元之间的订单还是太多，没法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。
二.计数排序（Countingsort）~
个人觉得，计数排序其实是桶排序的一种特殊情况。当要排序的n个数据，所处的范围并不大的时候，比如最大值是k，我们就可以把数据划分成k个桶。每个桶里的数据值都是相同的，省掉了桶内排序的时间。
我们都经历过高考，高考差分数系统你还记得吗？查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生，如何通过成绩快速排序得出每次呢？
考生的满分是分，最小是0分，这个数据范围很小，所以我们可以分成个桶，对应分数从0分到分。根据考生的成绩，我们将这50万考生划分到这个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了50万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是O(n)。
计数排序的算法思想就是如此简单，跟桶排序非常类似，只是桶的大小粒度不一样。不过，排序算法里的“计数”含义来自哪里呢？
这个问题和计数排序算法的实现方法有关。
还是拿考生那个例子来解释。为了方便说明，假设只有8个考生，分数在0到5分之间。这8个考生的成绩我们放在一个数组A[8]中，它们分别是2，5，3，0，2，3，0，3。
考生的成绩从0到5分，我们使用大小为6的数组C[6]表示桶，其中下标对应分数。不过，C[6]内存储的并不是考生，而是对应的考生分数。像刚刚举的那个例子，我们只需要遍历一遍考生分数，就可以得到C[6]的值。
从图中可以看出，分数为3分的考生有3个，小于3分的考生有4个，所以，成绩为3分的考生在排序之后的有序数组R[8]中，会保持在下标4，5，6的位置。
那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？用到了一个非常巧妙的处理方法。
思路如下：对C[6]数组顺序求和，C[6]存储的数据就变成了下面这个样子。C[k]里存储小于等于分数k的考生个数。
接下来是计数排序中最复杂、最难理解的一部分。
我们从后到前依次扫描数组A，这里是从后到前是为了保证算法的稳定性。比如，当扫描到3时，我们可以从数组C中取出下标为3的值7，也就是说，到目前为止，包括自己在内，分数小于等于3的考生有7个，也就是说3是数组R中的第7个元素（也就是数组R中下标为6的位置）。当3放入到数组R中，小于等于3的元素就只剩下6个了，所以相应的C[3]要减1，变成6。
以此类推，当我们继续从后往前扫描到第二个分数为3的考生的时候，就会把它放入到数组R中的第6个元素的位置（也就是下标为5的位置）。当我们扫描完整个数组A后，数组R内的数据就是按照分数从小到大有序排列的了。
代码如下：
//计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。publicvoidcountingSort(int[]a,intn){if(n=1)return;//查找数组中数据的范围intmax=a[0];for(inti=1;in;++i){if(maxa){max=a;}}int[]c=newint[max+1];//申请一个计数数组c，下标大小[0,max]for(inti=0;i=max;++i){c=0;}//计算每个元素的个数，放入c中for(inti=0;in;++i){c[a]++;}//依次累加for(inti=1;i=max;++i){c=c[i-1]+c;}//临时数组r，存储排序之后的结果int[]r=newint[n];//计算排序的关键步骤，有点难理解for(inti=n-1;i=0;--i){intindex=c[a]-1;//之所以要-1是因为数组计数从0开始r[index]=a;//从后往前，a为原数组，c为计数数组c[a]--;}//将结果拷贝给a数组for(inti=0;in;++i){a=r;}}这种利用另外一个数组来计数的实现方式是不是很巧妙呢？这也是这种排序算法叫计数排序的原因。
总结一下，计数排序只能用在数据范围不大的场景中，如果数据范围k要比要排序的数据n大很多哦，就不适合用计数排序了，因为这样就不容易有重复情况了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数，因为要用到计数数组。
比如，还是拿考生这个例子。如果考生成绩精确到小数点后一位。就需要将所有的分数都乘以10，转化成整数，然后再放到0个桶内。再比如，如果要排序的数据中有负数，数据的范围是[-,]，那我们就需要先对每个数据都加，转化为非负整数。
三.基数排序（Radixsort）~
再来看这样一个排序问题。假设我们有10万个手机号码，希望将这10万个手机号码从小到达排序，有什么比较快速的排序方法？
上面的快排，时间复杂度可以做到O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序并不能派上用场，因为手机号码有11位，范围太大。那针对这个排序问题，有没有时间复杂度是O(n)的算法呢？有的，就是基数排序。
刚刚这个问题里，有这样的规律：假设要比较两个手机号码a，b的大小，如果在前面几位中，a手机号码已经比b手机号码大了，那后面几位就不用看了。也就是说，要尽可能地考虑到位。
借助稳定排序算法，这里有一个巧妙的实现思路，先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过11次排序之后，手机号码就都有序了。
手机号码稍微长了点，不好画图。于是用字符串按照基数排序的过程分解图来作为示意图。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
而根据每一位来排序，可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到O(n)。如果要排序的数据有k位，那我们就需要k次桶排序或者计数排序，总的时间复杂度是O(k*n)。当k不大的时候，比如手机号码排序的例子，k最大就是11，所以基数排序的时间复杂度就近似于O(n)。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的20万个英文单词，最短的只有1个字母，最长的有45个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？
这时候我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII值，所有字母都大于“0”，补“0”不会影响到到原有的大小顺序。这样就可以继续用基数排序了。
总结一下，基数排序对要排序的数据的要求是，数据需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a数据的高位比b数据达，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到O(n)了。
四.如何根据年龄给万用户排序~
实际上，这个问题就类似按照成绩给50万考生排序。假设年龄范围最小1岁，最大不超过岁。可以遍历这万用户，根据年龄将其划分到这个桶里，然后依次顺序遍历这个桶中的元素。这样就得到了按照年龄排序的万用户数据。
1.假设我们现在需要对D，a，F，B，c，A，z这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序后为a，c，z，D，F，B，A，该如何实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母放在前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么实现呢？
用两个指针a、b：a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素；重复如上过程，直到a、b指针相交。
对于小写字母放前面，数字放中间，大写字母放后面，可以先将数据分为小写字母和非小写字母两大类，进行如上交换后再在非小写字母区间里分为数字和大写字母做同样处理。
但这种做法并不是稳定的算法，刚好这里不要求有序。
也就是当只有两个大类时优先考虑使用交换位置的算法，这样就可以实现原地排序，最小时间复杂度。
排序优化：如何实现一个通用的、高性能的排序函数？
几乎所有的编程语言都会提供排序函数，比如C语言中qsort()，C++STL中的sort()、stable_sort()，还有Java语言中的Collections.sort()。平时开发中，我们也都是直接使用这些现成的函数来实现业务逻辑中的排序功能。那这些排序函数是如何实现的？底层都利用了哪种排序算法？
一.如何选择合适的排序算法？
如果要实现一个通用的、高效率的排序函数，我们应该选择哪种排序算法？先回顾一下上面几种排序算法。
之前讲过，线性排序算法虽然时间复杂度比较低，但适用场景比较特殊。故如果要写一个通用的排序函数，就不能选择线性排序算法。
如果对小规模数据进行排序，可以选择时间复杂度是O(n^2)的算法；如果是对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。
时间复杂度是O(nlogn)的排序算法不止一个，比如上面的归并排序、快速排序，以及后面的堆排序。堆排序和快速排序都有比较多的应用，比如Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数。
会发现，使用归并排序的情况其实并不多。快排最坏情况下的时间复杂度是O(n^2)，而归并排序可以做到平均情况、最坏情况下的时间复杂度都是O(nlogn)，但它的空间复杂度是O(n)，并不是原地排序算法。粗略夸张地说，如果要排序MB的数据，除了数据本身占用的内存之外，排序算法还要额外再占用MB的内存空间，内存耗费翻倍了。
上面说过，快速排序比较适合来实现排序函数，但快排在最坏情况下时间复杂度是O(n^2)，如何来解决这个“复杂度恶化”的问题呢？
二.如何优化快速排序？
为什么最坏情况下快速排序的时间复杂度是O(n^2)，上面说过，如果原来的数据是有序的或者接近有序的，而每次分区点都选择最后一个数据，那快速排序算法就会把变成非常糟糕，时间复杂度就会退化成O(n^2)。也就是说，这种O(n^2)时间复杂度出现的主要原因是因为我们分区点选得不够合理。
那如何来选择好的分区点呢？
最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。
如果很粗暴地直接选择第一个或者最后一个数据作为分区点，不考虑数据的特点，肯定会出现之前那样，在某些情况下，排序的最坏情况时间复杂度是O(n^2)。所以为了提高排序算法的性能，我们也要尽可能地让每次分区都比较平均。
三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这3个数的中间值作为分区点。这样每间隔固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数”取中可能就不够了，可能要“五数取中”或者“十数取中”。
随机法
随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。这种方法并不能保证每次分区点都选的比较好，但是从概率的角度来看，也不大可能会出现每次分区点都选得很差的情况，所以，平均情况下，这样选的分区点是比较好的。时间复杂度退化为最糟糕的O(n^2)的情况，出现的可能性并不大。
我们知道，快速排序是用递归来实现的。而递归要警惕堆栈溢出。为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了首先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈出栈的过程，就没有了系统栈大小的限制。
三.举例分析排序函数
拿Glibc中的qsort()函数举例说明一下，虽说qsort()从名字上看，很像是基于快速排序算法，但实际上它并不仅仅使用了快排这一种算法。
如果去看源码，会发现，qsort()会优先使用归并排序来排序输入数据，因为归并排序的空间复杂度是O(n)，所以对于小数据量的排序，比如1KB、2KB的内存空间，归并排序额外需要1KB、2KB的内存空间，这时候问题不大。因为现在计算机的内存都挺大的，很多时候追求的是速度，这就是一个典型的用空间换时间的应用。
但如果数据量太大，比如排序MB的数据，这时候再用归并排序就不合适了。所以，要排序的数据量比较大的时候，qsort()会改为用快速排序算法来排序。
那qsort()是如何选择快速排序算法的分区点呢？如果去看源码，你会发现，qsort()选择分区点的方法就是“三数取中法”，也并不复杂。
还有递归太深会导致堆栈溢出的问题，qsort()是通过自己实现一个堆上的栈，手动模拟递归来解决的。
实际上，qsort()并不仅仅用到了归并排序和快速排序，它还用到了插入排序。在快速排序的过程中，当要排序的区间中，元素的个数小于等于4时，qsort()就退化为插入排序，不再继续用递归来做快速排序，因为在小规模数据面前，O(n^2)时间复杂度的算法并不一定比O(nlogn)的算法执行时间长。
算法的性能是可以通过时间复杂度来分析，但是，实际上这种复杂度分析是比较偏理论的，如果深究的话，实际上时间复杂度并不等于代码实际的运行时间。
时间复杂度代表的是一个增长趋势，如果画成增长曲线图，会发现O(n^2)比O(nlogn)要陡峭，也就是增长趋势要更猛一些。但是，在大O表示法中，我们会省略低阶、系数和常数，也就是说，O(nlogn)在没有省略低阶、常数、系数之前可能是O(knlogn+c)，而且k和c有可能还是一个比较大的数。
假设k=，c=，当我们对小规模数据（比如n=）排序时，n^2的值实际上比klogn+c还要小。
knlogn+c=**log+远大于0n^2=*=0所以，对于小规模数据的排序，O(n^2)的排序算法并不一定比O(nlogn)排序算法执行的时间长。对于小数据量的排序，我们选择比较简单、不需要递归的插入排序算法。
而在qsort()插入排序的算法实现中，也利用了哨兵这种来简化代码，提高执行效率的编程技巧。虽然哨兵可能只是少做一次判断，但是毕竟排序函数是非常常用、非常基础的函数，性能的优化要做到极致。
最后，希望你把思考的过程看得比标准答案更重要。
1.能否分析一下你熟悉的语言中的排序函数都是用什么排序算法实现的？都有哪些优化技巧？
查看了下Array.sort的源码，主要采用TimSort算法，大致思路是这样的：
元素个数32，采用二分查找插入排序（BinarySort），二分插入排序是在插入排序的基础上引入了二分查找的思想，也就是在有序区中采用二分查找算法进行插入位置的确定;
元素个数=32，采用归并排序，归并的核心是分区（Run），分区的意思比如就是将一个数组分为左右两个区间;
找连续升或降的序列作为分区，分区最终被调整为升序后压入栈；
如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阈值；
每次压入栈，都有检查栈内已存在的分区是否满足合并条件，满足则进行合并；
最终栈内的分区被全部合并，得到一个排序好的数组。
Timsort的合并算法非常巧妙：
找出左分区最后一个元素（最大）及在右分区的位置；
找出右分区第一个元素（最小）及在左分区的位置；
仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的。
而Java1.8中的排序，在元素小于47时用插入排序，大于47小于用双轴排序，大于用timsort归并排序，并在timsort中记录数据的连续的有序段的位置，若有序段太多，也就是说数据近乎乱序，则用双轴排序，当然快排的递归调用的过程中，若排序的子数组数据量小，用插入排序。
补充说明：双轴排序是和单轴快排区分的，单轴快排就是普通的快速排序。而双轴快排是选取两个主元素将区间划分为3部分的快排。
预览时标签不可点收录于话题#个上一篇下一篇