Java算法是Java面试必考必问的，今天给大家总结13道常见的Java算法面试题及答案，希望对大家所有帮助@mikechen
算法的时间复杂度时候是什么？
算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。
其中f(n)是问题规模n的某个函数，这样用大写O( )来体现算法时间复杂度的记法，我们称之为大O记法。
常见的时间复杂度有哪些？
主要有以下8种：
- 常数阶 O(1)
- 对数阶 O(log2n)
- 线性阶 O(n)
- 线性对数阶 O(nlog2n)
- 平方阶 O(n^2)
- 立方阶 O(n^3)
- k 次方阶 O(n^k)
- 指数阶 O(2^n)
常见的时间复杂度排序？
常见的算法时间复杂度由小到大一次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n)
如下图所示：
随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
Java常见的排序算法有哪些？
常见的内部排序算法有：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序等。
Java排序算法的时间与空间复杂度？
什么是插入排序算法？
插入排序的思想打牌的人肯定很容易理解，就是见缝插针。
首先就默认数组中的第一个数的位置是正确的，即已经排序，然后取下一个数，与已经排序的数按从后向前的顺序依次比较， 如果该数比当前位置排好序的数小，则将排好序的数的位置向后移一位。
重复上一步骤，直到找到合适的位置，找到位置后就结束比较的循环，将该数放到相应的位置。
如何编写插入排序算法？
//插入排序
public static void insertSort(int[] arr){
//用于记录数据以及下标
int temp = 0 , j = 0;
//从第二个数（即 i = 1）开始进行对前面进行插入
for(int i = 1; i < arr.length; i++){
//记录这个数以及下标
temp = arr[i];
j = i;
//记录下的temp比它前面的数（j - 1）要小，则往前插入，当j = 0时为最前面的数了，所以结束
while (j > 0 && temp <arr[j - 1]){
//直接让在自己前面的数将自己覆盖（可以看成是前面的数往后退了），因为已经用temp记录下来了
arr[j] = arr[j-1];
//然后继续往前找
j--;
}
//循环结束后，则说明已经找到了位置，而且下标为j，直接插入即可
arr[j] = temp;
}
}
什么是选择排序？
选择排序也是一种简单直观的排序算法，实现原理比较直观易懂：
首先在未排序数列中找到最小元素，然后将其与数列的首部元素进行交换，然后，在剩余未排序元素中继续找出最小元素，将其与已排序数列的末尾位置元素交换。以此类推，直至所有元素圴排序完毕，如下图所示：
如何编写选择排序？
//选择排序
public static void selectionSort(int[] arr){
//定义一个数，用于记录找到的数
int temp = 0;
//第一层for循环为执行的总次数，因为执行到倒数第二个数是，数组已经有序，故arr.length -1
for(int i = 0; i < arr.length -1; i++){
//用于记录下标
int index = i;
//这里是从i开始后的所有数都要进行比较
for (int j = i + 1;j < arr.length; j++){
//如果发现有比arr[i]大的，则更新下标，这样是为了最终找到最小的那个数的下标
if (arr[index] > arr[j]){
index = j;
}
}
//如果进入循环前的i发生了变化，则证明有数更小，并且更小的数，下标为j，直接交换即可
if (index != i){
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}
}
什么是希尔排序？
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题，希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组。
希尔排序算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
如何编写希尔排序？
//希尔排序
public static void SellSort(int[] arr){
/*不停对 原数组 进行分组，step为每个数组的元素之间 的距离
（这里是看作是不同数组，实际在同一个数组中）
不停的缩小距离（step），则是将数组分得更小，直到step = 1（成为一个数组）
*/
for(int step = arr.length/2; step > 0 ; step = step/2){
/*
从下标step开始为一个数组的第二个数，然后进行插入排序
step + 1 为下一个数组第二个数，进行插入排序，以此类推
*/
for (int i = step ; i < arr.length; i++){
//这操作与插入排序相同，结合插入排序理解
//记录数以及下标
int j = i;
int temp = arr[j];
//数组的前一个数（arr[j - step]）比trmp大则继续插入，当(j - step) > 0 则说明已经到了数组最前面的数
while ((j - step) > 0 && arr[j - step] > temp){
arr[j] = arr[j - step];
j = j - step;
}
//找到位置则插入
arr[j] = temp;
}
}
}
什么是冒泡排序？
冒泡排序是大部分人最容易想到的排序，即对n个数进行排序，每次都是由前一个数跟后一个数比较，每循环一轮， 就可以将最大的数移到数组的最后， 总共循环n-1轮，完成对数组排序。
如何编写冒泡排序算法
//冒泡排序
public static void bubbleSort(int[] arr){
//用来记录数据，便于互换数据
int temp = 0;
//当倒数第二个数确定，则无需继续排序。故为arr.length -1次
for (int i = 0; i < arr.length -1; i++){
/*从第一个数开始，让它跟往后一个数进行比较，然后如此类推，因为第一层每执行完一趟，
都会确定数组末尾的一个数，已确定的数不需要加入比较，固有arr.length - i
同时，每一次剩最后两个数时只需要执行一次，所以arr.length - i -1次
*/
for (int j = 0;j < arr.length - i - 1; j++ ){
//如果发现后一个数比前一个数小，则相互交换位置
if(arr[j] > arr[j+1]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
作者简介
陈睿|mikechen，10年+大厂架构经验，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读mikechen更多原创技术文章👇
阿里架构 |双11秒杀 |微服务 |云原生 |Docker |K8S |Kafka |分布式架构 |高并发架构
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》