冒泡算法java实现

import java.util.Arrays;

public class Bubbling {
    public static void main(String args[]) {

        int array[] = {6, 5, 4, 3, 2, 1, 0};
        sort(array);
        sort2(array);

    }

    /**
     * O((n-1)+(n-2)+(n-3)...1)=O((n-1)*n/2)=O(1/2*n^2-1/2*n)=O(n^2)
     * 1,2,3,4,5,6=(7+7+7)=(n+1)*n/2=1/2n^2+1/2n=21
     * 这是一种冒泡法的实现，不过这种排序是循环的与每一个元素进行比较，无论数据如何分布都会进行比较，用的是内外层循环比较。
     *
     * @param array
     */
    public static void sort(int array[]) {
        int n = 0;
        if (array == null || array.length < 2) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            int a = array[i];
            n++;
            //循环从下一个元素开始，与之后的每一个元素比较，如果其比我小，我就与其交换
            for (int j = i + 1; j < array.length; j++) {
                int b = array[j];
                if (a > b) {
                    array[i] = b;
                    array[j] = a;
                    a = b;
                }
                n++;
            }
            System.out.println(Arrays.toString(array));

        }
        System.out.println(n);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 与上一个排序不同，所有的元素比较都是在内层做的，每一个都与下一个比较，大于则交换位置，所以末尾的是最大的一个。
     * 这样的好处是：能够判断出元素没有进行过比较交换的操作，顺序就是递增的，不需要进行比较了，从而避免了无效的比较操作。
     * 时间复杂度：
     * 1.最坏情况：与上一种一样。
     * 2.最好情况：O(n-1)=O(n)
     *
     * @param array
     */
    public static void sort2(int array[]) {
        int n = 0;
        if (array == null || array.length < 2) {
            return;
        }
        boolean swap = false;
        for (int i = 0; i < array.length - 1; i++) {//只需要比较n-1次，因为最后一个不需要比较，所以范围-1
            n++;
            //循环从下一个元素开始，与之后的每一个元素比较，如果其比我小，我就与其交换
            for (int j = 0; j < array.length - i - 1; j++) {
                int a = array[j];
                //j+1的位置，所以j判断的范围需要缩小1个
                int b = array[j + 1];
                //内层循环的每一个都与下一个比较
                if (a > b) {
                    array[j + 1] = a;
                    array[j] = b;
                    swap = true;
                }
                n++;
            }
            System.out.println(Arrays.toString(array));
            //如果数据已经是按照从小到大的顺序了，那么就不用再比较了
            if (!swap) {
                break;
            }

        }
        System.out.println(n);
        System.out.println(Arrays.toString(array));
    }

}