面试时常常考察的java排序算法--选择排序、冒泡排序、插入排序

简介: 面试时常常考察的java排序算法--选择排序、冒泡排序、插入排序

注:本文是从java语言角度对三种排序算法进行分析比较。

一、选择排序

核心思想:

依次拿当前元素和其后面的元素比较大小,满足条件就互换值

public static int[] shunxu(int[] arr){
  int len = arr.length;
  int temp = 0;
  for (int i = 0; i < len-1; i++) {
    for (int j = i+1; j < len; j++) {
      if(arr[i] > arr[j]){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

解读:

arr[i]是当前元素,范围是[0,arr.length-1)

arr[j]是当前元素后面的元素,范围是[i+1,arr.length)

时间复杂度:

最好的情况是所有数字都是有序的,对于n位的数组,时间复杂度为O(n);


最坏的情况是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所以时间复杂度为o(n(n-1)/2)

二、冒泡排序

核心思想:

依次拿相邻的元素做比较,满足条件就互换值。

每轮比较找到一个最值(最大或者最小),把其放到末尾

public static int[] maopao(int[] arr){
  int len = arr.length;
  int temp = 0;
  for (int i = 0; i < len-1; i++) {
    for (int j = 0; j < len-1-i; j++) {
      if(arr[j] > arr[j+1]){
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  return arr;
}

解读:

外层for循环表示比较轮数,范围是[0,arr.length-1),总共比较了length-1轮


内层for循环表示第 i 轮比较的次数,范围是[0,arr.length-1-i)


每一轮都会产生一个最值(最大值或最小值),则下一轮就少比较一次


外层for循环控制比较的总轮数,该循环是以内层for循环的变量 j 作为数组的下标进行比较时间复杂度:

最好的情况同选择排序,即所有数字都是有序的,对于n位的数组,时间复杂度为O(n);


最坏的情况同顺序排序,是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所有时间复杂度为o(n(n-1)/2)

三、插入排序

核心思想:

假设前面的数字是有序的,依次拿当前元素与前面元素做比较,满足条件就互换值

public static int[] charu(int[] arr){
  int len = arr.length;
  int temp = 0;
  for (int i = 1; i < len; i++) {
    for (int j = i; j > 0; j--) {
      if(arr[j] > arr[j-1]){
        temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
      }else{
        break;
      }
    }
  }
  return arr;
}

解读:

外层for循环控制轮数,范围是[1,arr.length)

从第2个数字开始,与前面的数字比较,满足条件就互换值,否则就放到当前位置(代码中有break)

时间复杂度:

最好的情况跟上面的相同,是所有数字都是有序的,对于n位的数组,时间复杂度为O(n);


最坏的情况跟上面的相同,是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所有时间复杂度为o(n(n-1)/2)

三种排序算法对比

根据时间复杂度来比较,三种排序算法的最好和最坏的值都是相同的。所以,我们无法从时间复杂度上面来对比他们。


我们可以从代码上面分析,由于插入排序代码里有一个break,以至于不满足条件的时候,直接中断内层for循环的执行。所以,相对于其它算法,它的比较次数相应的会少很多,所以效率会更快。


综合考虑的情况下,插入排序>=冒泡排序>=选择排序

与其它排序对比:

相关文章
|
26天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
62 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
24天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
15天前
|
搜索推荐
冒泡排序算法
【10月更文挑战第19天】冒泡排序是一种基础的排序算法,虽然在实际应用中可能不是最优的选择,但对于理解排序算法的基本原理和过程具有重要意义。
|
18天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
23天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
26天前
|
机器学习/深度学习 算法 搜索推荐
让星星⭐月亮告诉你,Java冒泡排序及其时间复杂度计算
冒泡排序是一种简单的排序算法,通过多次遍历数组,每次比较相邻元素并交换位置,将较小的元素逐步移至数组前端。第一轮结束后,最小值会位于首位;第二轮则将次小值置于第二位,依此类推。经过 (n-1) 轮遍历后,数组完成排序。冒泡排序的时间复杂度为 O(n²),在最优情况下(已排序数组)时间复杂度为 O(n)。示例代码展示了如何实现冒泡排序。
47 1
|
28天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
95 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
28天前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
70 0
|
28天前
|
搜索推荐 C语言
排序算法--冒泡排序
排序算法--冒泡排序
12 0
|
搜索推荐 Java
希尔排序(简单易懂,图文并貌,插入排序)java代码实现
希尔排序(简单易懂,图文并貌,插入排序)java代码实现
151 0
希尔排序(简单易懂,图文并貌,插入排序)java代码实现