数据结构与算法：冒泡排序

一、定义

冒泡排序是最基础的排序算法。

冒泡排序的英文是bubble sort，它是一种基础的交换排序。

冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。

二、思路

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位 置；当一个元素小于或等于右侧相邻元素时，位置不变。

经过第一轮后： 元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。

每一轮结束都会有一个元素被移到最右侧。

三、实现

1、冒泡算法

public static void mAIn(String[] args) {
    int[] array = {1,6,2,5,3,0,3,5,4};
    array = bubbleSortBySortedExchanged(array);
    for(int i =0 ; i < array.length; i++){
        System.out.println(array[i]);
    }

}

    public static int[] bubbleSort(int[] array){
        //有array.length-1个数字需要交换
        for(int i = 0; i < array.length - 1; i++){
            //每个数字比较的次数是array.length-1-i
            for(int j = 0; j < array.length - 1 - i; j++){
                //如果当前值大于后一个值，则将更大的值移到后一位
                if(array[j] > array[j+1]){
                    swap(array[j],array[j+1]);
                }
            }
        }
        return array;
    }

   //互相交换值
    public static void swap(int a,int b){
        int temp = a;
        a  = b;
        b  = temp;
    }

2、冒泡算法优化

（1）外层优化

第6轮已经可以结束了，也就是如果不需要交换了，则说明已经排好序了

思路：在外层循环处，设置标志isSort，默认为排好，如果不交换则跳出本次循环

（2）内部优化

已经被移到右侧的元素不用再参与比较了

思路：设置lastExchangeIndex标志单轮比较中最后一次比较的数值下标，下一轮比较就以lastExchangeIndex结束。

private static  int[] bubbleSortBySortedExchanged(int[] array){
    if(array == null || array.length < 2){
        return array;
    }
    //单轮比较中最后一次交换的数值下标
    int lastExchangeIndex = 0;
    int sortBorder = array.length - 1;
    //不交换则表示已排好
    boolean isSorted = true;
    for(int i = 0 ;i < array.length - 1; i++){
        for(int j = 0; j < sortBorder ; j++){
            if(array[j] > array[j+1]){
                isSorted = false;
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if(isSorted){
            break;
        }
    }
    return array;
}

四、复杂度

时间复杂度：O( n的2次方 )

空间复杂度：O(1)，也就是原地排序

稳定性:相等元素之间原有的先后顺序不变，也就是稳定排序