排序算法之冒泡排序

忘是亡心i 2022-10-20 05:29 211阅读 0赞

## 冒泡排序 ##

冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡，看心情），依次比较相邻的两个数的大小（到底是比大还是比小也看你心情）  
![在这里插入图片描述][20191204155048636.gif_pic_center]

java代码实现bubblesort冒泡排序

package com.zy.test;
    
    
    import java.util.Arrays;
    
    public class BubbleSort { 
        public static void main(String[] args) { 
                System.out.println("sortTest");
                int[] arr={ 6,3,8,2,9,1};
            System.out.println(Arrays.toString(arr));
                for (int i=0;i<arr.length-1;i++){ 
                    for (int j=0;j<arr.length-1-i;j++){ 
                        int temp = 0;
                        if (arr[j]>arr[j+1]) { 
                            temp = arr[j];
                            arr[j] = arr[j+1];
                            arr[j+1] = temp;
                        }
                    }
                }
            System.out.println(Arrays.toString(arr));
        }
    }

冒泡排序思路：

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。  
    Java实现冒泡排序优化

**冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说.**

比如我举个数组例子：\[ 5，6，7，8，9 \]，一个有序的数组，根本不需要排序，它仍然是双层循环一个不少的把数据遍历干净，这其实就是做了没必要做的事情，属于浪费资源。

针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。

package com.zy.test;
    
    
    import java.util.Arrays;
    
    public class BubbleSort { 
        public static void main(String[] args) { 
                System.out.println("sortTest");
                int[] arr={ 6,3,8,2,9,1};
            System.out.println(Arrays.toString(arr));
                for (int i=0;i<arr.length-1;i++){ 
                    boolean flag=true;
                    for (int j=0;j<arr.length-1-i;j++){ 
                        int temp = 0;
                        if (arr[j]>arr[j+1]) { 
                            flag=false;
                            temp = arr[j];
                            arr[j] = arr[j+1];
                            arr[j+1] = temp;
                        }
                    }if (flag){ 
                        break;
                    }
                }
            System.out.println(Arrays.toString(arr));
        }
    }

[20191204155048636.gif_pic_center]: /images/20221020/3a85bdf5ce8948efb76e17fc2426cb07.png