冒泡排序及其优化方案
原创冒泡排序及其优化方案
原创
一只胡说八道的猴子
修改于 2020-11-02 10:39:33
修改于 2020-11-02 10:39:33
冒泡排序及其优化（以升序为例）
排序流程：
步骤1.从头开始比较相邻的两个元素，如果后面一个比前面一个小就交换位置，这样执行一轮最后的一个就是最大元素
步骤2.忽略之前找到的最大元素，重复执行步骤1，直到全部元素有序
**图例**
在这里插入图片描述
**代码实现**
package bubblesort;
public class sort1 {
public static void main(String[] args) {
int[] arr={1,4,5,2,6,8,4,5};
int end=arr.length-1;
for (;0<=end;end--){
for (int start=0;start<end;start++){
if (arr[start]>arr[start+1]){
int temp=arr[start];
arr[start]=arr[start+1];
arr[start+1]=temp;
}
}
}
for (int i=0;i< arr.length;i++){
System.out.println(arr[i]);
}
}
}优化方案1：
如果我们排序到一半的时候这个数组就已经有序了，那么我们为什么还要继续排序呢，这不是浪费资源吗，所有我们通过一下的方案来解决，在每次进行排序的时候都判断一下该排序是不是已经有序了
**实现方案**
package bubblesort;
public class sort1 {
public static void main(String[] args) {
int[] arr={1,4,5,2,6,8,4,5};
int end=arr.length-1;
for (;0<=end;end--){
//添加flag作为是不是已经有序的判断条件
boolean falg=true;
for (int start=0;start<end;start++){
if (arr[start]>arr[start+1]){
int temp=arr[start];
arr[start]=arr[start+1];
arr[start+1]=temp;
falg=false;
}
}
//如果flag等于true就说明数组已经有序了，
// 在这一轮没有进入交换环节，所以退出循环
if (falg==true){
break;
}
}
for (int i=0;i< arr.length;i++){
System.out.println(arr[i]);
}
}
}复杂度：
空间复杂度O(1)
时间复杂度:最好O(n）即一次循环后就退出
最差O(n^2) 即全部循环了才有序优化方案二
在我们进行排序之前数组就已经局部有序了，那么我们就不用花多余的时间对末尾的数组数据进行排序了
**如下图，数组的末尾已经局部有序了**
在这里插入图片描述
**实现方案**
package bubblesort;
public class sort3 {
public static void main(String[] args) {
int[] arr={1,4,5,2,6,8,4,5};
int end=arr.length-1;
for (;0<=end;end--){
//sortIndex的值可以取小于等于1的任何值
//以为如果原来就有序了，那么就需要另end在第一次循环后就小于0
//令其退出循环
int sortIndex=1;
for (int start=0;start<end;start++){
if (arr[start]>arr[start+1]){
int temp=arr[start];
arr[start]=arr[start+1];
arr[start+1]=temp;
//记录最后一次交换数据的位置
sortIndex=start;
}
}
//只要循环到已经有序的数组之前即可
end=sortIndex;
}
for (int i=0;i< arr.length;i++){
System.out.println(arr[i]);
}
}
}复杂度：
空间复杂度O(1)
时间复杂度:最好O(n）即一次循环后就退出
最差O(n^2) 即全部循环了才有序算法的稳定性
排序算法是稳定的算法
以上就是冒泡排序算法及其优化方案，如有帮助还请点赞关注支持，如有疑问评论私信都可，看到后可帮助解答本博客主要侧重于数据结构于算法和java开发，操作系统，计算机网络，觉得我的文章有帮助的小伙伴可以关注我，有疑问可评论私信，相逢即是缘，大家高处见
在这里插入图片描述
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录