一、算法描述

冒泡排序：比如在一个长度为N的无序数组中，在第一趟从第一个数据开始遍历，遇到比他大的(小的）,就交换位置，直到最大的（最小的）排到最后。第二趟找出倒二大的，N-1趟之后，数组有序。

二、算法分析

三种方法实现

1、暴力穷举-------- 没什么好说的

2、比如数组2 1 3 4 5 6 7 8 9，第一轮排序后变为1 2 3 4 5 6 7 8 9，后面所有排序都是白白浪费时间，所以，应该在数组已经有序了就停止排序，而判断的标志就是，某一趟排序没有交换。

3、比如数组6 5 2 3 1 4 7 8 9，第一轮排序后变为5 2 3 1 4 6 7 8 9，按照第前两种排序，第二轮排序将从第一个元素遍历到第n-1个元素，但其实从 ‘‘6‘’ 开始，数组后边已经有序，不需要载排序了，所以我们可以用一个变量记录下最后一个发生交换的位置，下一次遍历到这个数就可以了。

三、算法实现

• java实现代码：

package sort;

public class BubbleSort{
        
    public static void main(String[] args) {
        int[] arr = {8 , 4, 6, 2, 7, 3, 1, 9 ,5};
        int[] result1 = bubbleSort1(arr);
        show(result1);
        int[] result2 = bubbleSort1(arr);
        show(result2);
        int[] result3 = bubbleSort1(arr);
        show(result3);
    }
    
    
    /**
     *  冒泡排序 从小到大排序 无优化
     * @param arr
     * @return
     */
    public static int[] bubbleSort1(int[] arr) {
        int n = arr.length;//长度
        int temp = 0;//中间变量
        
        for(int i = 0 ; i < n-1 ; i++) {
            for(int j = 0 ; j < n-i-1 ; j++) {
                //如果上边的泡泡更重(值更大)，则往下沉(交换)
                if(arr[j]>arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }
    
    /**
     *  冒泡排序 从小到大排序 优化一
     * @param arr
     * @return
     */
    public static int[] bubbleSort2(int[] arr) {
        int n = arr.length;//长度
        int temp = 0;//中间变量
        int count = 0;//计数器
        
        for(int i = 0 ; i < n-1 ; i++) {
            count = 0;//恢复为0
            for(int j = 0 ; j < n-i-1 ; j++) {
                //如果上边的泡泡更重(值更大)，则往下沉(交换)
                if(arr[j]>arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    count++;//交换次数+1
                }
            }
            if(count == 0) {//此轮排序无交换，数组已经有序
                break;//退出循环
            }
            
        }
        return arr;
    }
    
    /**
     *  冒泡排序 从小到大排序 优化二
     * @param arr
     * @return
     */
    public static int[] bubbleSort3(int[] arr) {
        int n = arr.length;//长度
        int temp = 0;//中间变量
        int count = 0;//计数器
        int k = n-1;//记录最后一次交换的位置,其后已经有序，初始值为n-1
        int flag = 0;
        
        for(int i = 0 ; i < n-1 ; i++) {
            count = 0;//恢复为0
            k = flag;
            for(int j = 0 ; j < k ; j++) {
                //如果上边的泡泡更重(值更大)，则往下沉(交换)
                if(arr[j]>arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    count++;//交换次数+1
                    flag = j+1;
                }
            }
            if(count == 0) {//此轮排序无交换，数组已经有序
                break;//退出循环
            }
            
        }
        return arr;
    }
    
    
    public static void show(int[] result) {
        for(int i = 0 ; i < result.length ; i++) {
            System.out.print(result[i]+" ");
        }
        System.out.println();
    }
}

所有内容均个人编辑，如有错误，欢迎指正！