Java常用的八种排序算法及代码实现+图解
作者:程序员的小傲娇 时间:2022-04-09 13:30:06
经典的排序算法有八种,分别为:
冒泡排序
选择排序
插入排序
归并排序
希尔排序
快速排序
堆排序
基数排序
其中冒泡排序、选择排序、插入排序称为三大基本排序。
虽然这三大基本排序算法时间复杂度都是O(n2),但是其实细细讨论之下,还是有各自的特点的。
1.冒泡排序
冒泡排序法的思路
基本思路:
假设我们需要进行升序排列
进行N轮的比较,每一轮将相邻的两个元素依次比较,根据大小进行交换,每轮比较结束后,将最大的元素依次‘冒’到数组的末尾,经过几轮比较后,数组就会呈现有序的状态。
图解:
2)后面每轮都按照此方法进行比较,但是需要注意,此后的每一轮都需要比前一轮少比较一次,因为前面已经确定了最大元素的位置,为了提高性能,可以不用再和后面确定了位置的元素进行比较。
3)由此可以确定,当数组的长度为N时,需要比较的轮数为N-1轮。每轮中从第一个元素开始相邻元素两两进行比较,第一轮需要比较N-1次,第2轮需要比较N-2次,依次类推,实现整体排序。
2.冒泡排序法的代码实现
首先通过一个外层的
for
循环确定比较的轮数,循环元素数量-1轮。内部通过一个
for
循环实现每轮的两两元素比较的效果。每轮需要比较的次数都会比上一轮减少一次,通过j元素两两比较通过
array[j] > array[j+1]
来实现。
3.冒泡排序法优化
以上的冒泡排序法还有优化的空间。因为如果一个数组已经是完全有序的情况下,冒泡排序法仍然会进行逐轮的比较,这无疑是浪费性能的行为。因此我们可以确定,当冒泡的比较中,有一轮如果没有发生交换,则可以确定当前数组已经完全有序,后面的轮数完全不必在进行。故做以下的调整:
通过定义一个标识符isSort
,如果有一轮没有发生任何交换,则isSort
就会为true
,下次直接break,后面的轮数就不用再进行比较了。
4.选择排序
选择排序的思路
基本思路:
选择排序和冒泡排序不同,选择排序会通过一轮比较,选出最小的那个元素的下标,然后和第一个元素进行交换,这样第一个元素的位置就可以确定了。
第二轮如法炮制,从第二个元素开始依次比较,选出最小的元素的下标,和第二个元素交换位置,这样第二小的元素位置就确定了。
后面依次类推,直到整个数组呈现有序状态。
选择排序法的代码实现:
选择排序比较的轮数和冒泡排序比较的轮数是一样的
K表示当前最小值的下标,当前是第几轮,k就先代表第几个元素的下标,然后依次和后面的元素进行比较,如果发现比k位置元素小的元素时,改变k的下标,这样一轮过后k代表的位置就是本轮最小的元素,和i进行交换即可
如果一轮过后k==i,则说明i本来就是最小的元素,则无需交换提高性能。
5.插入排序
插入排序的思路
基本思路:
假设一个数组已经基本有序,则这个时候插入排序就是一个不错的选择。插入排序是先保证左边元素是基本有序的,然后将后面的元素依次和左边元素进行比较,如果比较到一个比自己小的元素时就可以停止比较了,因为左边已经呈现有序状态,找到比自己小的元素时,就不用再往后比较了。
插入排序的代码实现:
插入排序的轮数和冒泡排序一样,但是i从1开始,因为我们假设第一个元素已经是呈现有序状态了。
内部循环依次从当前位置开始,和前面元素进行比较,如果找到了比自己小的元素,则停止比较,直接退出本轮比较,进行下一轮比较
总结:
虽然三种排序法的时间复杂度都是O(N2),但是不同的场景还是会有不同的性能差异。
冒泡排序法是性能最差的算法,正式运用中,基本不会用冒泡排序法进行排序。
选择排序将交换次数降到最低,但是比较次数仍然很大。当数据量小,并且交换耗时相对于比较耗时更多的情况下,选择排序是个不错的选择。
基本有序的情况下,插入排序是最好的选择,但是如果数据基本逆序的情况下,插入排序的性能和冒泡排序就基本一样了。
从平均情况下来看,插入排序性能会比选择排序略好一些。
来源:https://blog.csdn.net/xiaoxijinger/article/details/122121783
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Windows下Java环境变量配置详解
基于C语言string函数的详解
使用Swing绘制动态时钟
![](https://img.aspxhome.com/file/2023/6/59166_0s.gif)
Spring Cloud Alibaba使用Nacos作为注册中心和配置中心
![](https://img.aspxhome.com/file/2023/3/67983_0s.png)
Java为什么基本数据类型不需要进行创建对象?
Springboot项目全局异常统一处理案例代码
Java8 HashMap键与Comparable接口小结
![](https://img.aspxhome.com/file/2023/3/60563_0s.jpg)
JAVA技术实现上传下载文件到FTP服务器(完整)
Java微信公众平台开发(13) 微信JSSDK中Config配置
![](https://img.aspxhome.com/file/2023/9/67439_0s.jpg)
详解maven中profiles使用实现
![](https://img.aspxhome.com/file/2023/2/64512_0s.jpg)
Java内存模型(JMM)及happens-before原理
![](https://img.aspxhome.com/file/2023/2/59972_0s.png)
java按指定编码写入和读取文件内容的类分享
java数据结构与算法之noDups去除重复项算法示例
Default Methods实例解析
springboot整合shiro多验证登录功能的实现(账号密码登录和使用手机验证码登录)
浅谈Spring中Bean的作用域、生命周期
![](https://img.aspxhome.com/file/2023/7/59567_0s.png)
在spring中手写全局异常拦 截器
Java判断变量是否为空问题的方法总结
java代码实现C盘文件统计工具
![](https://img.aspxhome.com/file/2023/4/67664_0s.png)
Java 设计模式中的命令模式详情
![](https://img.aspxhome.com/file/2023/3/59683_0s.png)