面试基础-冒泡排序

        多年的开发经验仍不能透彻理解一些基础的算法，按说懂个大概也行啊，言语稍微变通一下就可以啦，可更重要的是言语表达也是不在行，遇到一些姿态较高的，又爱跟你较真和抬扛的人的时候，就无奈了。想想算了吧，随他吧。可是你自己呢，别人看到的你仍是小白啊，那我就把自己当作小白，重新来过吧。
        没有系统的按照教科书的顺序，只按自己想到哪，学到哪，记录到哪。

下面进入正题，先来个冒泡排序。一个最简版本，一个稍微优化版本。

测试输入：new int[]{1, 17, 6, 9, 2, 4, 100, 38, 94, 29, 46, 3, 57, 65, 19, 5};

    /**
     * 最差的冒泡排序
     * n*(n-1)次比较，0-n*(n-1)次交换
     *
     * @param arr
     */
    public void sort0(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    Util.swap(arr, j, j + 1);
                    swapTimes++;
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:240 交换次数:46

    /**
     * 稍优化一点的冒泡排序
     * n*(n-1)/2次比较，（0-n*(n-1)/2）次交换
     *
     * @param arr
     */
    public void sort(int[] arr) {
        int compareTimes = 0;
        int swapTimes = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                compareTimes++;
                if (arr[j] > arr[j + 1]) {
                    swapTimes++;
                    Util.swap(arr, j, j + 1);
                }
            }
        }
        System.out.println("数组长度:" + arr.length + " 比较次数:" + compareTimes + " 交换次数:" + swapTimes);
    }

打印输出：数组长度:16 比较次数:120 交换次数:46

时间复杂度均为O(n^2)

code地址：https://github.com/angelala00/learn/blob/master/src/main/java/cn/jc/datastructure/sort/BubbleSort.java