AI 助理
备案控制台
开发者社区 Java技术栈 文章 正文

Java面试中经常问到的算法题

2021-12-10 207
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从大学到现在，参加过很多面试，经常会被问到一些基本的算法题，而大部分算法的理论及思想，我们曾经都能倒背如流，并且也用语言实现过，可由于在项目开发中应用的比较少，久而久之就忘记了，造成在面试中很尴尬的局面，然后回来查阅相关资料才发现就那么一回事，怎么在面试中就卡壳了呢？在此写下我在面试中经常被问到的一些基本的算法，全当复习。

 从大学到现在，参加过很多面试，经常会被问到一些基本的算法题，而大部分算法的理论及思想，我们曾经都能倒背如流，并且也用语言实现过，可由于在项目开发中应用的比较少，久而久之就忘记了，造成在面试中很尴尬的局面，然后回来查阅相关资料才发现就那么一回事，怎么在面试中就卡壳了呢？在此写下我在面试中经常被问到的一些基本的算法，全当复习。

一、冒泡排序

Java代码 
package sort.bubble;   
import java.util.Random;   
/**  
 * 依次比较相邻的两个数，将小数放在前面，大数放在后面  
 * 冒泡排序，具有稳定性  
 * 时间复杂度为O（n^2）  
 * 不及堆排序，快速排序O（nlogn，底数为2）  
 * @author liangge  
 *  
 */  
public class Main {   
    public static void main(String[] args) {   
        Random ran = new Random();   
        int[] sort = new int[10];   
        for(int i = 0 ; i < 10 ; i++){   
            sort[i] = ran.nextInt(50);   
        }   
        System.out.print("排序前的数组为");   
        for(int i : sort){   
            System.out.print(i+" ");   
        }   
        buddleSort(sort);   
        System.out.println();   
        System.out.print("排序后的数组为");   
        for(int i : sort){   
            System.out.print(i+" ");   
        }   
    }   
    /**  
     * 冒泡排序  
     * @param sort  
     */  
    private static void buddleSort(int[] sort){   
        for(int i=1;i<sort.length;i++){   
            for(int j=0;j<sort.length-i;j++){   
                if(sort[j]>sort[j+1]){   
                    int temp = sort[j+1];   
                    sort[j+1] = sort[j];   
                    sort[j] = temp;   
                }   
            }   
        }   
    }   
}  
package sort.bubble;
import java.util.Random;
/**
 * 依次比较相邻的两个数，将小数放在前面，大数放在后面
 * 冒泡排序，具有稳定性
 * 时间复杂度为O（n^2）
 * 不及堆排序，快速排序O（nlogn，底数为2）
 * @author liangge
 *
 */
public class Main {
  public static void main(String[] args) {
    Random ran = new Random();
    int[] sort = new int[10];
    for(int i = 0 ; i < 10 ; i++){
      sort[i] = ran.nextInt(50);
    }
    System.out.print("排序前的数组为");
    for(int i : sort){
      System.out.print(i+" ");
    }
    buddleSort(sort);
    System.out.println();
    System.out.print("排序后的数组为");
    for(int i : sort){
      System.out.print(i+" ");
    }
  }
  /**
   * 冒泡排序
   * @param sort
   */
  private static void buddleSort(int[] sort){
    for(int i=1;i<sort.length;i++){
      for(int j=0;j<sort.length-i;j++){
        if(sort[j]>sort[j+1]){
          int temp = sort[j+1];
          sort[j+1] = sort[j];
          sort[j] = temp;
        }
      }
    }
  }
}

二、选择排序

Java代码 
package sort.select;   
import java.util.Random;   
/**  
 * 选择排序  
 * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，  
 * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。   
 * 选择排序是不稳定的排序方法。  
 * @author liangge  
 *   
 */  
public class Main {   
    public static void main(String[] args) {   
        Random ran = new Random();   
        int[] sort = new int[10];   
        for (int i = 0; i < 10; i++) {   
            sort[i] = ran.nextInt(50);   
        }   
        System.out.print("排序前的数组为");   
        for (int i : sort) {   
            System.out.print(i + " ");   
        }   
        selectSort(sort);   
        System.out.println();   
        System.out.print("排序后的数组为");   
        for (int i : sort) {   
            System.out.print(i + " ");   
        }   
    }   
    /**  
     * 选择排序  
     * @param sort  
     */  
    private static void selectSort(int[] sort){   
        for(int i =0;i<sort.length-1;i++){   
            for(int j = i+1;j<sort.length;j++){   
                if(sort[j]<sort[i]){   
                    int temp = sort[j];   
                    sort[j] = sort[i];   
                    sort[i] = temp;   
                }   
            }   
        }   
    }   
}  
package sort.select;
import java.util.Random;
/**
 * 选择排序
 * 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
 * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 
 * 选择排序是不稳定的排序方法。
 * @author liangge
 * 
 */
public class Main {
  public static void main(String[] args) {
    Random ran = new Random();
    int[] sort = new int[10];
    for (int i = 0; i < 10; i++) {
      sort[i] = ran.nextInt(50);
    }
    System.out.print("排序前的数组为");
    for (int i : sort) {
      System.out.print(i + " ");
    }
    selectSort(sort);
    System.out.println();
    System.out.print("排序后的数组为");
    for (int i : sort) {
      System.out.print(i + " ");
    }
  }
  /**
   * 选择排序
   * @param sort
   */
  private static void selectSort(int[] sort){
    for(int i =0;i<sort.length-1;i++){
      for(int j = i+1;j<sort.length;j++){
        if(sort[j]<sort[i]){
          int temp = sort[j];
          sort[j] = sort[i];
          sort[i] = temp;
        }
      }
    }
  }
}

三、快速排序

Java代码 
package sort.quick;   
/**  
 * 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，  
 * 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
 * @author liangge  
 *   
 */  
public class Main {   
    public static void main(String[] args) {   
        int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };   
        System.out.print("排序前的数组为：");   
        for (int data : sort) {   
            System.out.print(data + " ");   
        }   
        System.out.println();   
        quickSort(sort, 0, sort.length - 1);   
        System.out.print("排序后的数组为：");   
        for (int data : sort) {   
            System.out.print(data + " ");   
        }   
    }   
    /**  
     * 快速排序  
     * @param sort 要排序的数组  
     * @param start 排序的开始座标  
     * @param end 排序的结束座标  
     */  
    public static void quickSort(int[] sort, int start, int end) {   
        // 设置关键数据key为要排序数组的第一个元素，   
        // 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小   
        int key = sort[start];   
        // 设置数组左边的索引，往右移动判断比key大的数   
        int i = start;   
        // 设置数组右边的索引，往左移动判断比key小的数   
        int j = end;   
        // 如果左边索引比右边索引小，则还有数据没有排序   
        while (i < j) {   
            while (sort[j] > key && j > start) {   
                j--;   
            }   
            while (sort[i] < key && i < end) {   
                i++;   
            }   
            if (i < j) {   
                int temp = sort[i];   
                sort[i] = sort[j];   
                sort[j] = temp;   
            }   
        }   
        // 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，   
        // 即保持了key左边的数比key小，key右边的数比key大   
        if (i > j) {   
            int temp = sort[j];   
            sort[j] = sort[start];   
            sort[start] = temp;   
        }   
        //递归调用   
        if (j > start && j < end) {   
            quickSort(sort, start, j - 1);   
            quickSort(sort, j + 1, end);   
        }   
    }   
}  
package sort.quick;
/**
 * 快速排序 通过一趟排序将要排序的数据分割成独立的两部分， 其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行，以此达到整个数据变成有序序列。
 * @author liangge
 * 
 */
public class Main {
  public static void main(String[] args) {
    int[] sort = { 54, 31, 89, 33, 66, 12, 68, 20 };
    System.out.print("排序前的数组为：");
    for (int data : sort) {
      System.out.print(data + " ");
    }
    System.out.println();
    quickSort(sort, 0, sort.length - 1);
    System.out.print("排序后的数组为：");
    for (int data : sort) {
      System.out.print(data + " ");
    }
  }
  /**
   * 快速排序
   * @param sort 要排序的数组
   * @param start 排序的开始座标
   * @param end 排序的结束座标
   */
  public static void quickSort(int[] sort, int start, int end) {
    // 设置关键数据key为要排序数组的第一个元素，
    // 即第一趟排序后，key右边的数全部比key大，key左边的数全部比key小
    int key = sort[start];
    // 设置数组左边的索引，往右移动判断比key大的数
    int i = start;
    // 设置数组右边的索引，往左移动判断比key小的数
    int j = end;
    // 如果左边索引比右边索引小，则还有数据没有排序
    while (i < j) {
      while (sort[j] > key && j > start) {
        j--;
      }
      while (sort[i] < key && i < end) {
        i++;
      }
      if (i < j) {
        int temp = sort[i];
        sort[i] = sort[j];
        sort[j] = temp;
      }
    }
    // 如果左边索引比右边索引要大，说明第一次排序完成，将sort[j]与key对换，
    // 即保持了key左边的数比key小，key右边的数比key大
    if (i > j) {
      int temp = sort[j];
      sort[j] = sort[start];
      sort[start] = temp;
    }
    //递归调用
    if (j > start && j < end) {
      quickSort(sort, start, j - 1);
      quickSort(sort, j + 1, end);
    }
  }
}

四、插入排序

Java代码 
package sort.insert;   
/**  
 * 直接插入排序  
 * 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据  
 * 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。  
 */  
import java.util.Random;   
public class DirectMain {   
    public static void main(String[] args) {   
        Random ran = new Random();   
        int[] sort = new int[10];   
        for (int i = 0; i < 10; i++) {   
            sort[i] = ran.nextInt(50);   
        }   
        System.out.print("排序前的数组为");   
        for (int i : sort) {   
            System.out.print(i + " ");   
        }   
        directInsertSort(sort);   
        System.out.println();   
        System.out.print("排序后的数组为");   
        for (int i : sort) {   
            System.out.print(i + " ");   
        }   
    }   
    /**  
     * 直接插入排序  
     *   
     * @param sort  
     */  
    private static void directInsertSort(int[] sort) {   
        for (int i = 1; i < sort.length; i++) {   
            int index = i - 1;   
            int temp = sort[i];   
            while (index >= 0 && sort[index] > temp) {   
                sort[index + 1] = sort[index];   
                index--;   
            }   
            sort[index + 1] = temp;   
        }   
    }   
}  
package sort.insert;
/**
 * 直接插入排序
 * 将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据
 * 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
 */
import java.util.Random;
public class DirectMain {
  public static void main(String[] args) {
    Random ran = new Random();
    int[] sort = new int[10];
    for (int i = 0; i < 10; i++) {
      sort[i] = ran.nextInt(50);
    }
    System.out.print("排序前的数组为");
    for (int i : sort) {
      System.out.print(i + " ");
    }
    directInsertSort(sort);
    System.out.println();
    System.out.print("排序后的数组为");
    for (int i : sort) {
      System.out.print(i + " ");
    }
  }
  /**
   * 直接插入排序
   * 
   * @param sort
   */
  private static void directInsertSort(int[] sort) {
    for (int i = 1; i < sort.length; i++) {
      int index = i - 1;
      int temp = sort[i];
      while (index >= 0 && sort[index] > temp) {
        sort[index + 1] = sort[index];
        index--;
      }
      sort[index + 1] = temp;
    }
  }
}

 

五、顺便贴个二分搜索法

Java代码 

package search.binary;   
public class Main {   
    public static void main(String[] args) {   
        int[] sort = {1,2,3,4,5,6,7,8,9,10};   
        int mask = binarySearch(sort,6);   
        System.out.println(mask);   
    }   
    /**  
     * 二分搜索法，返回座标，不存在返回-1  
     * @param sort  
     * @return  
     */  
    private static int binarySearch(int[] sort,int data){   
        if(data<sort[0] || data>sort[sort.length-1]){   
            return -1;   
        }   
        int begin = 0;   
        int end = sort.length;   
        int mid = (begin+end)/2;   
        while(begin <= end){   
            mid = (begin+end)/2;   
            if(data > sort[mid]){   
                begin = mid + 1;   
            }else if(data < sort[mid]){   
                end = mid - 1;   
            }else{   
                return mid;   
            }   
        }   
        return -1;   
    }   
}
文章标签：
Java
算法
关键词：
Java算法
Java面试
算法java
面试算法
算法面试
开发工程师
目录
相关文章
BigFour
|
19天前
|
设计模式 算法 搜索推荐
Java 设计模式之策略模式：灵活切换算法的艺术
策略模式通过封装不同算法并实现灵活切换，将算法与使用解耦。以支付为例，微信、支付宝等支付方式作为独立策略，购物车根据选择调用对应支付逻辑，提升代码可维护性与扩展性，避免冗长条件判断，符合开闭原则。
BigFour
200 35
游客cxuvnylemktao
|
2月前
|
算法 Java
50道java集合面试题
50道 java 集合面试题
游客cxuvnylemktao
227 72
啦啦啦191
|
5月前
|
缓存 Java 关系型数据库
2025 年最新华为 Java 面试题及答案，全方位打造面试宝典
Java面试高频考点与实践指南（150字摘要） 本文系统梳理了Java面试核心考点，包括Java基础（数据类型、面向对象特性、常用类使用）、并发编程（线程机制、锁原理、并发容器）、JVM（内存模型、GC算法、类加载机制）、Spring框架（IoC/AOP、Bean生命周期、事务管理）、数据库（MySQL引擎、事务隔离、索引优化）及分布式（CAP理论、ID生成、Redis缓存）。同时提供华为级实战代码，涵盖Spring Cloud Alibaba微服务、Sentinel限流、Seata分布式事务，以及完整的D
啦啦啦191
305 1
啦啦啦191
|
4月前
|
缓存 Java API
Java 面试实操指南与最新技术结合的实战攻略
本指南涵盖Java 17+新特性、Spring Boot 3微服务、响应式编程、容器化部署与数据缓存实操，结合代码案例解析高频面试技术点，助你掌握最新Java技术栈，提升实战能力，轻松应对Java中高级岗位面试。
啦啦啦191
413 0
一枚后端工程狮
|
30天前
|
存储 算法 搜索推荐
《数据之美》：Java数据结构与算法精要
本系列深入探讨数据结构与算法的核心原理及Java实现，涵盖线性与非线性结构、常用算法分类、复杂度分析及集合框架应用，助你提升程序效率，掌握编程底层逻辑。
一枚后端工程狮
131 8
爱吃烤鸡翅的酸菜鱼
|
26天前
|
存储 人工智能 算法
从零掌握贪心算法Java版：LeetCode 10题实战解析（上）
在算法世界里，有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择，寄希望于通过局部最优达成全局最优。这种思想就是贪心算法，它以其简洁高效的特点，成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想，并通过10道LeetCode经典题目实战演练，带你掌握这种"步步为营"的解题思维。
爱吃烤鸡翅的酸菜鱼
194 0
啦啦啦191
|
4月前
|
Java 数据库连接 数据库
Java 相关知识点总结含基础语法进阶技巧及面试重点知识
本文全面总结了Java核心知识点，涵盖基础语法、面向对象、集合框架、并发编程、网络编程及主流框架如Spring生态、MyBatis等，结合JVM原理与性能优化技巧，并通过一个学生信息管理系统的实战案例，帮助你快速掌握Java开发技能，适合Java学习与面试准备。
啦啦啦191
202 2
Java 相关知识点总结含基础语法进阶技巧及面试重点知识
游客cxuvnylemktao
|
2月前
|
算法 Java
50道java基础面试题
50道java基础面试题
游客cxuvnylemktao
71 0
盹猫
|
4月前
|
机器学习/深度学习 算法 Java
Java实现林火蔓延路径算法
记录正在进行的森林防火项目中林火蔓延功能,本篇文章可以较好的实现森林防火蔓延,但还存在很多不足,如:很多参数只能使用默认值,所以蔓延范围仅供参考。(如果底层设备获取的数据充足,那当我没说)。注:因林火蔓延涉及因素太多,如静可燃物载量、矿质阻尼系数等存在估值,所以得出的结果仅供参考。
盹猫
62 4

Java技术栈

热门文章

最新文章

  • 1
    百宝箱开放平台 ✖️ Java SDK
  • 2
    【Azure Storage Account】Java Code访问Storage Account File Share的上传和下载代码示例
  • 3
    《深入理解Spring》：现代Java开发的核心框架
  • 4
    Java 设计模式之策略模式：灵活切换算法的艺术
  • 5
    Java 设计模式之状态模式：让对象的行为随状态优雅变化
  • 6
    Java语言实现字母大小写转换的方法
  • 7
    java零基础学习者入门课程
  • 8
    Java 设计模式之观察者模式：构建松耦合的事件响应系统
  • 9
    Java 设计模式之责任链模式：优雅处理请求的艺术
  • 10
    grpc-java 架构学习指南
  • 1
    面试性能测试总被刷？学员真实遇到的高频问题全解析！
    83
  • 2
    提供一些准备Java八股文面试的建议
    169
  • 3
    Redis常见面试题全解析
    311
  • 4
    C++面试周刊(3):面试不慌,这样回答指针与引用，青铜秒变王者
    398
  • 5
    Python面试题精选及解析
    133
  • 6
    字节面试： MySQL 百万级 导入发生的 “死锁” 难题如何解决？“2序4拆”，彻底攻克
    351
  • 7
    Redis数据类型面试给分情况
    119
  • 8
    Java 面试实操指南与最新技术结合的实战攻略
    413
  • 9
    MyBatis场景面试题
    245
  • 10
    大厂RAG面试题：24个RAG八股文。偷偷背下来，毒打面试官 ！
    849

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0
    • 下一篇
    阿里云对象存储OSS收费标准：500G存储118元1年、