三大类算法：递归、排序、二分查找

一、递归

”递“＋”归“。 这两个意思，正是递归思想的精华所在，去的过程叫做递，回来的过程叫做归，在编程语言中对递归可以简单理解为：方法自己调用自己，只不过每次调用时参数不同而已。

满足递归的条件：

1、递归表达是（规律）

如果一个问题的解能够拆分成多个子问题的解，拆分之后，子问题和该问题在求解上除了数据规模不一样之外，求解的思路和该问题的求解思路完全相同，也就是说能够找到一种规律，这种规律就是我们说的递推公式，那么这个问题就可以使用递归来求解。

比如之前的例2关于电影院座位的例子，你要知道“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。

2、终止递归的条件（递归出口）

把一个问题的解分解为多个子问题的节，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。就比如电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是 f(1)=1，这就是递归的终止条件。

递归的问题：

问题1：堆栈溢出

int main(){
    int a =1;
    int b =0;
    int c =0;
    b =add(3,5);
    c=a+b;
    return 0;
}

int add(intx ,int y){
    int sum =o;
    sum=x+y;
    return sum;
}

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,称为函数调用栈。用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

通过图我们发现，递归代码在执行的过程中，每一次递归的调用都会向函数调用栈中压入临时变量，知道满足递归终止条件在回归的过程中才会一次的将临时变量压出 栈，如果递归调用的层次很深，一致在压入栈，虚拟机的栈的空间一般都不大，所以如果一直入栈就会出现栈内存溢出。

我们在写代码的时候如何避免堆栈溢出呢，我们可以在写代码的时候限制递归调用的最大深度，比如递归调用超过10000次后就不再继续递归调用了，直接返回或抛出异常。但是其实这样做并不能完全的解决问题，因为当前线程能允许的最大递归深度其实跟当前剩余的栈空间大小有关系，事先是不知道有多大的，如果想知道就得实时的去计算剩余的栈空间大小，这样也会影响我们的性能，所以说如果递归的深度不是特别大的话是可以使用这种方式来防止堆栈溢出的，否则的话这种办法也不合适。

问题2：重复计算

出现重复计算的问题，比如斐波那契数列，（Fibonacci sequence）

斐波那契数列是这样的一组数，1、1、2、3、5、8、13、21、34，现在需要求出第n个数是多少

从第三个数开始，每一项的数都是前两项数的和，也就是我们可以找到递推公式，当n>=3时，f（n）=f（n-1）+f（n-2）其中f（2）=1，f（1）=1

public static int fibonacci(int n){
    if(n==1){
        return 1;
    }else if(n==2){
        retrun1;
    }else{
        return(fibonacci(n-1)+fibonacci(n-2));
    }
}

这里面会有重复计算的问题，比如我们求解f（5），是f（4）+f（3）求解图如下。

可以看出f（3），被重复计算的多次，这就是重复计算的问题。那么如何避免重复计算呢。

我们可以通过一个数据结构（散列表），来保存已经求解过的f（k），当递归调用到f（k）时，先看下是否已经求解过了，如果是，则直接从散列表中取值返回，不需要重复计算，这样就避免重复问题，散列表后面会写到。

递归和循环

递归是有去有回，循环是有去无回

例如：

int f(int n){
    if(n==1){
        return 1;
    }
    return f(n-1)+1;
}

如果改写成非递归的形式

int f(int n){
    int ret =1;
    for(int i=2;i<=n;i++){
        ret=ret+1;
    }
    return ret;
}

我们可以使用迭代循环的方式将递归代码改写为非递归代码，循环都可以写成递归，但是递归未必都能写成循环。

递归的应用：

1、阶乘的运算

阶乘问题数学表达式：n！=n*(n-1)*(n-2)*....*1(n>1)，比如我们要求解5的阶乘

public class Factorial{

    public int factorial(int n){

        if(n==0){
        return 1;
        }
    
        return factorial(n-1)*n;
    }
    
    @Test
    public void factorialTest(){
        System.out.println(factorial(5));
    }

}

public class Factorial{


    public BigInteger factorial(int n){
        if(n==0){
        return 1;
        }
        return BigInteger.valueOf(n).multiply(factorial(n-1));
    }
    @Test
    public void factorialTest(){
        System.out.println(factorial(100));    
    }

}

2、目录拷贝

通过java程序拷贝一个目录下的所有文件及目录到另一个目录下。

public class CopyDir{
    /**
     *高效拷贝目录 
     *
    /
    public void copyDir(File source ,File target){
            if(source.isFile()|| !source.exists()){
                return ;
            }
            //在目标目录下创建原目录
            File newDir = new File(target,source.getName());
            newDir.mkdir();
        
            //获取原目录下的所有文件和目录
            File[] listFiles = source.listFiles();
            //遍历判断是文件还是目录，是文件则直接进行拷贝工作，是目录则递归调用自己的实现拷贝
            for(File listFile : listFiles){    
                if(listFiles.isFile()){
                    //如果是文件则直接拷贝
                    try{
                        BufferedInpuStream bis = new BufferedInputStream(new FileInputStream(listFile));
                        BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream(new File(newDir,listFile.getName())));
                        int len =0;
                        byte[] bytes= new byte[1024*8];
                        while((len=bis.read(bytes))!=-1){
                            bos.write(bytes,0,len);
                        }
                        bos.close();
                        bis.close();
                        }catch(FileNotFoundException e){
                          e.printStackTrace();

                       }catch(IOException e){
                            e.printStackTrace();
                        }
                }else{
                    //如果是目录就递归拷贝 
                    copyDir(listFile,newDir);
                }
            
            }
            
    }


        @Test
        public void testCopyDir(){
           //创建原目录
            File source = new File("D:\\io\\source");
           //创建目标目录
            File target = new File("D:\\io\\target");
            //实现拷贝
            copyDir(source,target);
        }

}

二、排序算法

如果按照时间复杂度来分类大致可以分为三类：O(n2),冒泡排序、选择排序、插入排序；O(n*logn) 归并排序、快速排序，  O(n)：计数排序、基数排序、桶排序。。就复杂度而言：冒泡，插入，选择都是O(n2)，归并和快排是：O(n logn)；种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序，因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

判断排序算法的好坏，从三个方面来看

时间复杂度

空间复杂度

算法稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变

例如：有一组数据：3 7 2 7 5 8 9，我们按照大小排序之后的数据为：2 3 5 7 7 8 9，在这组数据中有两个7，如果经过某种排序算法后两个7的前后顺序没有发生改变则称该算法是稳定的排序算法，否则称为该算法是不稳定的排序算法。

冒泡排序

原理，它通过依次比较两个相邻的的元素，看两个元素是否满足大小关系，如果前一个元素比后一个元素大，前一个元素就与后一个元素交换。由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

总结

1：冒泡排序的时间复杂度是多少？
最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以 最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
2：冒泡排序的空间复杂度是多少？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一种in-place排序算法。
3：冒泡排序是稳定的排序算法吗？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

插入排序

原理,将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素，插入排序算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

算法描述如下：
• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

总结，插入排序的时间复杂度是多少？

1：如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好时间复杂度为 O(n)。注意，这里是从尾到头遍历已经有序的数据。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数 据，所以最坏情况时间复杂度为 O(n2)。还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是 O(n2)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n2)。

2：插入排序的空间复杂度是多少？
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个in-place【原地排序】排序算法。
3：插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

2：插入排序的空间复杂度是多少？
从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个in-place【原地排序】排序算法。
3：插入排序是稳定的排序算法吗？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

选择排序

原理

选择排序(Selection Sort)的原理有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从排序区间中找到最小的元素，将其放到已排序区间的末尾。

总结
1：选择排序的时间复杂度是多少？
结合之前的分析方式分析可知选择排序的最好情况时间复杂度为O(n2)，最坏情况时间复杂度为:O(n2)，平均情况下的时间复杂度为：O(n2)。
2：选择排序的空间复杂度是多少？
通过算法的实现我们可以发现，选择排序的空间复杂度为O(1)，是一个in-place排序算法
3：选择排序是一个稳定的排序算法吗？
注意：选择排序不是一个稳定的排序算法，为什么呢？选择排序每次都要找剩余未排序元素中的最小值，并和未排序区间的第一个元素进行交换位置，这样破坏了稳定性，比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，从稳定性上来说选择排序相对于冒泡排序和插入排序就稍微逊色了。

归并排序

原理

归并排序的核心思想，如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排序好的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的是分治思想，分治，分而治之，将一个大问题分解成小的问题解决，小的问题解决了，大的问题也就解决了。分治思想跟前民的递归思想很像。分治算法一般都是用递归来实现的。分治是一种解决处理思想，递归是一种编程技巧，

总结

1、得到归并排序的时间复杂度为：

从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)

2、归并排序的空间复杂度是多少？

实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

3、归并排序是稳定的排序算法

快速排序

原理，快速排序(Quick Sort)算法，简称快排，利用的也是分治的思想，初步看起来有点像归并排序，但是其实思路完全不一样

从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

总结
1：快速排序的时间复杂度是多少？
快排的时间复杂度最好以及平均情况下的复杂度都是O(nlogn)，只有在极端情况下会变成O(n2)
2：快速排序的空间复杂度是多少？
通过快排的代码实现我们发现，快排不需要额外的存储空间，所有的操作都能在既定的空间内完成，因此快排的空间复杂度为O(1)，也就是说快排是一种in-place的排序算法。
3：快速排序是稳定的排序算法吗？
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

快排和归并的异同

首先快排和归并都用到了分治递归的思想，在快排中对应的叫分区操作，递推公式和递归代码也非常相似，但是归并排序的处理过程是由下到上的由局部到整体，先处理子问题，然后再合并。而快排正好相反，它的处理过程 是由上到下由整体到局部，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是一种out-place排序算法。主要原因是合并函数无法在原地(数组内)执行。快速排序通过设计巧妙的原地(数组内)分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。

桶排序****

原理：桶排序(Bucket Sort)顾名思义，会用到“桶”，桶我们可以将其想象成一个容器，核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。换句话说：桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。

桶排序过程中存在两个关键环节：

1、元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上。

2、从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，每个桶内的排序算法的复杂度和稳定性，决定了最终的算法的复杂度和稳定性

桶排序比较适合用在非内存排序中。所谓的非内存排序就是说数据存储在外部磁盘中，数据量比较大，内 存有限，无法将数据全部加载到内存中。此外由桶排序的过程可知，当待排序集合中存在元素值相差较大时，对映射规则的选择是一个挑战，有时可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象，对算法的时间复杂度或空间复杂度有较大影响，所以桶排序适用于元素值分布较为集中的序列，或者说待排序的元素能够均匀分布在某一个范围[MIN, MAX]之间。

：比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。

理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
不过，你可能也发现了，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元…901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

接下来为了能对该算法做具体的实现，我们对该算法进一步做具体的描述：
• 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
• 从不是空的桶里把排好序的数据拼接起来。
注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。

总结：

1：桶排序的时间复杂度是多少？
桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，如果我们将待排序元素映射到某一个桶的映射规则做的很好的话，很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。我们一般对每个桶内的元素进行排序时采用快排也可以采用递归桶排序，通过我们刚开始的分析，当我们对每个桶采用快排时如果桶的个数接近数据规模n时，复杂度为O(n)，如果在极端情况下复杂度退化为O(n* log n)。
2：桶排序的空间复杂度是多少？
由于需要申请额外的空间来保存元素，并申请额外的空间来存储每个桶，所以空间复杂度为 O(N+M)，其中M代表桶的个数。所以桶排序虽然快，但是它是采用了用空间换时间的做法。
3：桶排序是稳定的排序算法吗？
桶排序是否稳定取决于对每一个桶内元素排序的算法的稳定性，如果我们对桶内元素使用快排时桶排序就是一个不稳定的排序算法。

计数排序***

排序算法总结：

三、二分查找法

二分查找的原理：二分查找(Binary Search)算法，也叫折半查找算法，二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。例如：假设有10个订单，其金额分别是：6，12，15，19，24，26，29，35，46，67。请从中找出订单金额为15的订单，利用二分查找的思想我们每次都与区间中间的数据进行大小的比较以缩小查找的范围，下面这幅图代表了查找的过程，其中 low，high代表了待查找区间的下标，mid表示待查找区间中间元素的下标(如果范围区间是偶数个导致中间数有两个就选择较小的那个)

二分查找的时间复杂度

通过分析其时间复杂度我们就可以发现，我们假设数据大小为n，每次查找完后数据的大小缩减为原来的一半，直到最后数据大小被缩减为1此时停止，如果我们用数据来描述其变化的规律那就是：

n，n/2，n/4，n/8，n/16，n/32，.......................，1；

可以看出来，这是一个等比数列，当数据大小变为1时：其中k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，通过计算k的值我们可以得出二分查找的时间复杂度就是 O(logn)，其中k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，通过计算k的值我们可以得出二分查找的时间复杂度就是 O(logn)。

这是一种非常高效的时间复杂度，有时候甚至比O(1)复杂度更高效，为什么这么说呢？因为对于log n来说即使n非常的大对应的log n的值也会很小，之前在学习O(1)复杂度时我们讲过O(1)代表的是一种常量级复杂度并不是说代码只需要执行一次，有时候可能要执行100次，1000次这种常数级次数的复杂度都可以用O(1)表示，所以，常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。

二分查找的实现

有序数列中不存在重复元素。

有序数列存在重复元素。

二分查找的使用条件及场景

通过我们之前的分析可以知道，二分查找的时间复杂度是O(log n)，其效率非常高，那是不是说所有情况下都可以使用二分查找。

1、待查找的数据序列必须有序

待查找的数据序列必须是有序的，假如数据无序，那我们要先排序，然后二分查找，通过前面排序算法的学习我们知道，如果我们针对的是一组固定的静态数据，也就说该数据序列不会进行插入和删除操作，那我们完全可以先排序然后二分查找，这样子一次排序多次查找；但是如果数据序列本身不是固定的静态的，可能涉及数据序列的插入和删除操作，那我们每次查找前都需要进行排序然后才能查找，这样子成本非常的高。

2、数据的存储依赖数组

待查找的数据序列需要使用数组进存储，也就是说依赖顺序存储结构。二分查找，算法需要根据下标，low,high,mid来访问数据序列中的元素，数组按照下标访问元素的复杂度是O(1)，而链表访问元素的时间复杂度是O(n)，因此如果使用链表来存储数据二分查找的时间复杂度就会变得很高。

3、数据量太小或太大都不适合用二分查找

数据量很小的情况下，没有必要使用二分查找，使用循环遍历就够了，因为只有在数据量比较大的情况下二分查找才能体出优势，不过在某些情况下即使数据量很小也建议大家使用二分查找，比如数据序列中的数据都是一些长度非常长的字符串，这些长度非常长的字符串比较起来也会非常的耗时，所以我们要尽可能的减少比较的次数，这样反倒有助于提高性能。

那为什么数据量太大的情况下也不建议使用二分查找呢？因为我们前面刚讲到二分查找底层需要依赖数组存储待查找的数据序列，而数组的特点是需要连续的内存空间，比如现在有1G的订单数据，如果用数组来存储就需要1G的连续内存，即便有2G的剩余内存空间，如果这2G的内存空间不连续那也无法申请到1G大小的数组空间，所以我们说数据量太大也不适合用二分查找。

总结：

1：复杂度分析：
分析方式：看循环次数最多的代码，加法原则，乘法原则
常见的复杂度量级：O(1) , O(n)，O(n* log n)，O(log n)
2：递归：
满足递归的条件：递推公式(规律)，递归终止条件
警惕递归的问题：堆栈溢出，重复计算
递归的应用：阶乘，目录拷贝等
3：排序：
常见排序算法的原理及实现：
冒泡，插入，选择，归并，快排，桶排序，计数排序

4：二分查找：