冒泡排序

分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(n^2)
最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
平均时间复杂度 ---- O(n^2)
所需辅助空间 ------ O(1)
稳定性 ------------ 稳定

原理

       它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

步骤

1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码实现

public class BubbleSort {
    void sort(Integer[] array){
          // 每次最大元素就像气泡一样"浮"到数组的最后
          for (int i = 0; i < array.length - 1 ; i++){
              // 依次比较相邻的两个元素,使较大的那个向后移
            for(int j = 0; j < array.length - 1 - i;j++){
                // 判断是否当前位置的数值大于下一个位置的数值，如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
                if (array[j] > array[j+1]){
                    //交换
                    Tool.exchange(array,j,j+1);
                }
            }
          }
    }

    public static void main(String[] args){
        Integer[] a = {3,4,1,9,5,2,6,10,20,16,13,11,0};
        BubbleSort sort = new BubbleSort();
        sort.sort(a);
        System.out.println("array by BubbleSort is " + Tool.arrayToString(a));
    }
}

public class Tool {
    public static <T> String arrayToString(T[] array){
        StringBuilder builder = new StringBuilder("[");
        for (int i = 0; i < array.length; i++){
            T item = array[i];
            builder.append(item + "");
            if (i != array.length - 1){
                builder.append(",");
            }
        }

        builder.append("]");
        return builder.toString();
    }

    public static <T> void exchange(T[] array, int i, int j){
        T temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

实现结果：

array by BubbleSort is [0,1,2,3,4,5,6,9,10,11,13,16,20]