面试必备——java算法面试题

算法是学习计算机的基础，更是学习编程必会的内容。在java程序员的面试中，对应聘者基础知识的掌握情况越来越重视，因此java算法面试题是大家在面试前必须要做的准备工作之一，下面整理了10道常考的java算法面试题，都是必会的基础题。

1、初级java排序算法的原理?

答：冒泡排序：重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

插入排序：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后)，直到全部插入排序完为止。

希尔排序：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

2、解释什么是冒泡排序算法?

答：冒泡排序算法也称为下沉排序。在这种类型的排序中，要排序的列表的相邻元素之间互相比较。如果它们按顺序排列错误，将交换值并以正确的顺序排列，直到最终结果“浮”出水面。

3、什么是复制回收算法?

答：把堆均分成两个大小相同的区域，只使用其中的一个区域，直到该区域消耗完。此时垃圾回收器终端程序的执行，通过遍历把所有活动的对象复制到另一个区域，复制过程中它们是紧挨着布置的，这样也可以达到消除内存碎片的目的。复制结束后程序会继续运行，直到该区域被用完。

但是，这种方法有两个缺陷：对于指定大小的堆，需要两倍大小的内存空间;需要中断正在执行的程序，降低了执行效率。

4、按代回收算法按代回收是为什么?

答：为什么要按代进行回收?这是因为不同对象生命周期不同，每次回收都要遍历所有存活对象，对于整个堆内存进行回收无疑浪费了大量时间，对症下药可以提高垃圾回收的效率。主要思路是：把堆分成若搞个子堆，每个子堆视为一代，算法在运行的过程中优先收集“年幼”的对象，如果某个对象经过多次回收仍然“存活”,就移动到高一级的堆，减少对其扫描次数。

5、解释二分法检索如何工作?

答：在二分法检索中，我们先确定数组的中间位置，然后将要查找的值与数组中间位置的值进行比较，若小于数组中间值，则要查找的值应位于该中间值之前，依此类推，不断缩小查找范围，直至得到最终结果。

6、解释是否可以使用二分法检索链表?

答：由于随机访问在链表中是不可接受的，所以不可能到达O(1)时间的中间元素。因此，对于链表来说，二分法检索是不可以的(对顺序链表或排序后的链表是可以用的)。

7、解释什么是堆排序?

答：堆排序可以看成是选择排序的改进，它可以定义为基于比较的排序算法。它将其输入划分为未排序和排序的区域，通过不断消除最小元素并将其移动到排序区域来收缩未排序区域。

8、解释一个算法的最佳情况和最坏情况之间有什么区别?

答：最佳情况：算法的最佳情况解释为算法执行最佳的数据排列。例如，我们进行二分法检索，如果目标值位于正在搜索的数据中心，则这就是最佳情况，最佳情况时间复杂度为0。

最差情况：给定算法的最差输入参考。例如快速排序，如果选择关键值的子列表的最大或最小元素，则会导致最差情况出现，这将导致时间复杂度快速退化到O(n2)。

9、使用递归算法输出某个目录下所有文件和子目录列表

答：

package com.bjsxt;

import java.io.File;

public class $ {

public static void main(String[] args) {

        String path = "D:/301SXT";

        test(path);

    }

    private static void test(String path) {

        File f = new File(path);

        File[] fs = f.listFiles();

        if (fs == null) {

            return;

        }

        for (File file : fs) {

            if (file.isFile()) {

                System.out.println(file.getPath());

            } else {

                test(file.getPath());

            }

        }

    }

10、说明一下java排序的基本概念是什么?

答：排序主要分为两类：内部排序和外部排序，java各种排序算法其实指的是内部排序算法。内部排序是基于内存的，整个排序过程都是在内存中完成的，而外部排序指的是由于数据量太大，内存不能完全容纳，排序的时候需要借助外存才能完成(常常是算计着某一部分已经计算过的数据移出内存让另一部分未被计算的数据进入内存)。

算法是学习java编程的基础，因为是否有一个扎实的基本功是面试官衡量是否能胜任java程序员岗位的一个标准，Java算法面试题更是基本功中的基本。当然这些题目肯定不能包含java算法的所有知识点，在java教程中会涵盖所有算法的内容。大家可以通过这10道java算法面试题来自测自己对算法的掌握程度怎么样，及时的查漏补缺。