Java最简洁数据结构之冒泡排序快速理解
作者:AXiYa_Ari 时间:2023-12-01 06:31:52
一、什么是冒泡排序
冒泡排序的英文是bubble sort,它是一种基础的交换排序。说到冒泡是不是就想起了快乐肥宅水呢?汽水中有许多小小的水泡哗啦哗啦的浮到上面来。这是因为组成小气泡的二氧化碳比水轻,所以小气泡可以一点一点地向上浮动。
而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身的大小,一点一点的向着数组的一侧移动。
二、图解冒泡排序
我们先看一个例子,有七个数字组成一个无序数列{5,6,3,4,1,7},对他进行冒泡排序。
按照冒泡排序的思想:把相邻的两个数字两两比较,当一个数字大于右侧相邻的数字时,交换他们的位置,当一个数字和他右侧的数字小于或等于的时候,不交换。
这样,作为数列中的最大的数字7就交换到了最右侧。这时第一轮冒泡结束。(有效区域只有最后一个)
根据第一轮的交换细节,第二轮到第六轮的状态为下图。
到此为止,所有的数字都是有序的了,冒泡排序是一种稳定排序,由于该排序算法的每一轮都要遍历所有的数字,一共要遍历n-1,所以时间复杂度为O(n^2)。
那么我们如何区分排序算法是否稳定呢?
如果我们交换的时候,遇到两个相同的数字,如果两个相同的数字在排序之后相对位置没有交换,那么就是稳定的排序,反之则是不稳定的排序。
三、代码实现
public static void bubbleSort(int arr[]){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j <arr.length-i-1 ; j++) {
int tmp=0;
if(arr[j]>arr[j+1]){
tmp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tmp;
}
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5,6,3,2,4,1,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
四、代码的优化
1、整体的思路
从上面的例子不难看出,我们可以对原来的冒泡排序进行优化。我们仍然用上面呢个数列{5,6,3,4,1,7}为例子,从上面的图解可以看出在第五轮排序后,整个数列已经是有序的,但是排序算法还是执行了第六轮排序。
优化的思路是:如果能判断出数列已经是有序的了,并且做出标记,那么就不会执行多余的排序。
所以我们可以用布尔变量isSorted作为标记,如果在本轮排序中有元素进行交换,则说明数列无序;如果在本轮排序中,没有元素进行交换,我们则认为此时数列已经为有序的,不需要再去进行下一轮的排序。
2、代码示例
public static void bubbleSort(int arr[]){
for (int i = 0; i < arr.length-1; i++) {
//有序标记,每一轮的初始值都是true
boolean isSorted=true;
for (int j = 0; j < arr.length-i-1; j++) {
int tmp=0;
if (arr[j]>arr[j+1]){
tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
//因为有元素进行交换,所以不是有序的,标记变为false
isSorted=false;
}
}
if (isSorted){
break;
}
}
}
public static void main(String[] args) {
int[] arr = new int[]{5,6,3,2,4,1,7};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
来源:https://blog.csdn.net/AXiYa_Ari/article/details/121295558
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
mybatis源码解读之executor包懒加载功能
Android应用程序(APK)的编译打包过程
![](https://img.aspxhome.com/file/2023/3/113433_0s.png)
Java判断字符串是否是整数或者浮点数的方法
Android轻松画出触摸轨迹
![](https://img.aspxhome.com/file/2023/7/96757_0s.jpg)
Flutter Flow实现滑动显隐层示例详解
Android多媒体之画画板开发案例分享
![](https://img.aspxhome.com/file/2023/8/126738_0s.gif)
Spring Data JPA 实体类中常用注解说明
![](https://img.aspxhome.com/file/2023/8/116108_0s.jpg)
springboot aspect通过@annotation进行拦截的实例代码详解
![](https://img.aspxhome.com/file/2023/6/113216_0s.png)
IDEA 2020.1 版自动导入MAVEN依赖的方法(新版MAVEN无法自动导入/更新POM依赖、MAVEN设置自动更新、自动更新快捷键)
![](https://img.aspxhome.com/file/2023/4/88504_0s.png)
为什么Java volatile++不是原子性的详解
Android之Spinner用法详解
springboot配置加密的正确姿势分享
![](https://img.aspxhome.com/file/2023/7/77157_0s.jpg)
c#序列化详解示例
Maven发布封装到中央仓库时候报错:no default secret key
Java--Socket通信(客户端服务端双向)
java组件commons-fileupload实现文件上传、下载、在线打开
![](https://img.aspxhome.com/file/2023/9/97789_0s.gif)