Java垃圾回收机制、系统设计、Android异步、排序算法

码仔，今天就给大家带来了《每日一道面试题》的第五期：

01

谈谈Java的垃圾回收机制以及触发时机 

内存回收机制：就是释放掉在内存中已经没有用的对象，要判断怎样的对象是没用的，有两种方法：

（1）采用标记数的方法，在给内存中的对象打上标记，对象被引用一次，计数加一，引用被释放，计数就减一，当这个计数为零时，这个对象就可以被回收，但是，此种方法，对于循环引用的对象是无法识别出来并加以回收的，

（2）采用根搜索的方法，从一个根出发，搜索所有的可达对象，则剩下的对象就是可被回收的，垃圾回收是在虚拟机空闲的时候或者内存紧张的时候执行的，什么时候回收并不是由程序员控制的，可达与不可达的概念：分配对象使用new关键字，释放对象时，只需将对象的引用赋值为null，让程序不能够在访问到这个对象，则称该对象不可达。

在以下情况中垃圾回收机制会被触发：

（1）所有实例都没有活动线程访问 ；

（2）没有其他任何实例访问的循环引用实例；

（3）Java中有不同的引用类型。判断实例是否符合垃圾收集的条件都依赖于它的引用类型

02

推荐系统设计 

推荐系统的任务就是联系用户和信息(物品),一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对它感兴趣的用户面前，从而实现信息消费者和信息生产者的双赢。

推荐系统很好满足了用户、平台、内容提供商三方的需求。以淘宝为例：用户及在淘宝上购物的买家，平台即淘宝网站，网站上众多的店主就是内容提供方。通过推荐系统可以更好将商品曝光给要购买的用户，提升社会资源的配置效率。

推荐系统落地到业务上需要大量的工程开发：涉及到日志打点、日志收集、ETL、分布式计算、特征工程、推荐算法建模、数据存储、提供接口服务、UI展示和交互、推荐效果评估等。

03

Android 实现异步的几种方式，原理与各自特点 

这边介绍三种：AsyncTask,HandlerThread和IntentService

AsyncTask原理：内部是Handler和两个线程池实现的，Handler用于将线程切换到主线程，两个线程池一个用于任务的排队，一个用于执行任务，当AsyncTask执行execute方法时会封装出一个FutureTask对象，将这个对象加入队列中，如果此时没有正在执行的任务，就执行它，执行完成之后继续执行队列中下一个任务，执行完成通过Handler将事件发送到主线程。AsyncTask必须在主线程初始化，因为内部的Handler是一个静态对象，在AsyncTask类加载的时候他就已经被初始化了。在Android3.0开始，execute方法串行执行任务的，一个一个来，3.0之前是并行执行的。如果要在3.0上执行并行任务，可以调用executeOnExecutor方法

HandlerThread原理：继承自Thread，start开启线程后，会在其run方法中会通过Looper创建消息队列并开启消息循环，这个消息队列运行在子线程中，所以可以将HandlerThread中的Looper实例传递给一个Handler，从而保证这个Handler的handleMessage方法运行在子线程中，Android中使用HandlerThread的一个场景就是IntentService

IntentService原理：继承自Service，它的内部封装了HandlerThread和Handler，可以执行耗时任务，同时因为它是一个服务，优先级比普通线程高很多，所以更适合执行一些高优先级的后台任务，HandlerThread底层通过Looper消息队列实现的，所以它是顺序的执行每一个任务。可以通过Intent的方式开启IntentService，IntentService通过handler将每一个intent加入HandlerThread子线程中的消息队列，通过looper按顺序一个个的取出并执行，执行完成后自动结束自己，不需要开发者手动关闭

04

简述几种排序算法的区别 

1.冒泡排序（BubbleSort）

算法简介：冒泡排序是一种简单的排序算法。

算法思想：它重复地走访要排序的数列，一次比较两个元素，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。

算法分析：冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。但是简单啊！！！

优点：稳定

缺点：慢，每次只能移动两个相邻的数据。

2.快速排序（QuickSort）

算法简介：快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。

算法思想：选择一个基准元素（一般选择序列最左边的值作为基准数据，其实基准的选择对算法是有影响的），将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序。

算法分析：快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，但对于内存非常有限的机器来说，它不是一个好的选择。

优点：极快，数据移动少；

缺点：不稳定（在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序）

3.归并排序（MergeSort）

算法简介：归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法思想：首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止。

算法分析：归并排序和选择排序（包括堆/直接选择）一样，归并排序的性能不受输入数据的影响，比选择排序稍微快一点，但是需要多一倍的内存空间，因为它需要一个额外的数组。

优点：稳定；

缺点：占内存

4.选择排序（SelectionSort）

算法简介：选择排序也是一种简单的排序。

算法思想：第一趟：从第一个记录开始，将后面n-1个记录进行比较，找到其中最小的记录和第一个记录进行交换；第二趟：从第二个记录开始，将后面n-2个记录进行比较，找到其中最小的记录和第2个记录进行交换；以此类推，直到最后。

算法分析：所以用到它的时候，数据规模越小越好，无论什么数据进去都是O(n2)的时间复杂度。唯一的好处可能就是不占用额外的内存空间了吧。

5.堆排序（Heapsort）

算法简介：堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法思想：堆排序会将所有的数据建成一个堆，最大的数据在堆顶（此堆为初始的无序区），然后将堆顶数据和序列的最后一个数据交换，由此得到新的无序区和有序区，且满足<=的值；接下来再次重建堆（因为交换后新的堆顶可能违反堆的性质，因此需要对当前无序区调整为新堆），交换数据，依次下去，就可以排序所有的数据。

算法分析：堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。

6.插入排序（InsertSort）

算法简介：插入排序是一种简单排序算法。

算法思想：将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。即先将序列的第一个记录看成是一个有序的子序列，然后从第二个记录逐个进行插入，直至整个序列有序为止。

算法分析：插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。但是它比冒泡排序快2倍。一般在数据大于1000或重复排序超过200的数据下使用。

优点：稳定，快

缺点：比较次数不一定，数据重复向后移动。

7.希尔排序（ShellSort）

算法简介：1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法思想：先将整个待排序元素序列分割成若干子序列（就是分成几个组且个数相同）（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

算法分析：Shell排序比冒泡排序快5倍，比插入排序大致快2倍。比快排，归并，堆排慢很多（有时在小数组中比快速排序和堆排序快）。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。

8.基数排序（RadixSort）

算法简介：基数排序和通常的排序算法并不走同样的路线，它是一种比较新颖的算法。

算法思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法分析：它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。

05

谈谈对运行结果的理解 

public static void main(String[] args){
 int i = 0;
 System.out.println((i++)+(++i)+(i++)+(++i));
 System.out.println(i);
}

主要是对前++、后++、赋值的理解

int a = i++; // a= 0, i = 1

int b = ++i; // b = 2, i = 2

int c = i++; // c = 2, i = 3

int d = ++i; // d= 4, i = 4

a + b + c + d; // 0 + 2 + 2 + 4 = 8

06

结束语 

如果你有好的答案可以提交至：

https://github.com/codeegginterviewgroup/CodeEggDailyInterview

往期文章：

今日问题：

周末大家都学习吗？

快来码仔社群解锁新姿势吧！社群升级：Max你的学习效率