图解Java排序算法之3种简单排序
排序是数据处理中十分常见且核心的操作,虽说实际项目开发中很小几率会需要我们手动实现,毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。本文简单温习下最基础的三类算法:选择,冒泡,插入。
先定义个交换数组元素的函数,供排序时调用
/** * 交换数组元素 * @param arr * @param a * @param b */ public static void swap(int []arr,int a,int b){ arr[a] = arr[a]+arr[b]; arr[b] = arr[a]-arr[b]; arr[a] = arr[a]-arr[b]; }
简单选择排序
简单选择排序是最简单直观的一种算法,基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。
在算法实现时,每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小,交换是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小元素之前,这些交换都是无意义的。我们可以通过设置一个变量min,每一次比较仅存储较小元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小元素的下标,此时再执行交换操作即可。代码实现很简单,一起来看下。
代码实现
/** * 简单选择排序 * * @param arr */ public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int min = i;//每一趟循环比较时,min用于存放较小元素的数组下标,这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; } } //进行交换,如果min发生变化,则进行交换 if (min != i) { swap(arr,min,i); } } }
简单选择排序通过上面优化之后,无论数组原始排列如何,比较次数是不变的;对于交换操作,在最好情况下也就是数组完全有序的时候,无需任何交换移动,在最差情况下,也就是数组倒序的时候,交换次数为n-1次。综合下来,时间复杂度为O(n2)
冒泡排序
冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素“浮”到顶端,最终达到完全有序
代码实现
在冒泡排序的过程中,如果某一趟执行完毕,没有做任何一次交换操作,比如数组[5,4,1,2,3],执行了两次冒泡,也就是两次外循环之后,分别将5和4调整到最终位置[1,2,3,4,5]。此时,再执行第三次循环后,一次交换都没有做,这就说明剩下的序列已经是有序的,排序操作也就可以完成了,来看下代码
/** * 冒泡排序 * * @param arr */ public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean flag = true;//设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已然完成。 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr,j,j+1); flag = false; } } if (flag) { break; } } }
根据上面这种冒泡实现,若原数组本身就是有序的(这是最好情况),仅需n-1次比较就可完成;若是倒序,比较次数为 n-1+n-2+...+1=n(n-1)/2,交换次数和比较次数等值。所以,其时间复杂度依然为O(n2)。综合来看,冒泡排序性能还还是稍差于上面那种选择排序的。
直接插入排序
直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。
代码实现
/** * 插入排序 * * @param arr */ public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int j = i; while (j > 0 && arr[j] < arr[j - 1]) { swap(arr,j,j-1); j--; } } }
简单插入排序在最好情况下,需要比较n-1次,无需交换元素,时间复杂度为O(n);在最坏情况下,时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下,插入排序还是要优于上面两种排序的。
总结
本文列举了排序算法中最基本的三种算法(简单选择,冒泡,插入),这三种排序算法的时间复杂度均为O(n2),后续会陆续更新其他更高阶一些的排序算法,时间复杂度也会逐步突破O(n2),谢谢支持。
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注猪先飞的更多内容!
原文出处:https://www.cnblogs.com/chengxiao/p/6103002.html
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19