Java简单排序之冒泡排序

排序原理:

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大
   值。

冒泡排序的图片展示.png

冒泡排序的代码实现:

    public static void bubbleSort(int[] a) {
        System.out.println("待排序数据: " + Arrays.toString(a));
        for (int i = 0; i < a.length - 1; i++) {
            //记录是否有元素互换的操作，如果没有元素互换的操作，说明已经提前排好，不需要继续排序了
            boolean isSort = false;
            //每循环一次，最后的数据肯定就是最大的了，所以就不需要在比较后面的数据了，所以结束条件j < a.length - 1 - i
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = temp;
                    isSort = true;
                }
            }
            System.out.println("第" + (i + 1) + "轮排序后的数组为: " + Arrays.toString(a));
            if (!isSort) {
                System.out.println("本轮中的两两比较未发生元素互换，代表排序已经完成啦");
                return;
            }
        }
    }

排序结果：

待排序数据: [4, 5, 6, 3, 2, 1]
第1轮排序后的数组为: [4, 5, 3, 2, 1, 6]
第2轮排序后的数组为: [4, 3, 2, 1, 5, 6]
第3轮排序后的数组为: [3, 2, 1, 4, 5, 6]
第4轮排序后的数组为: [2, 1, 3, 4, 5, 6]
第5轮排序后的数组为: [1, 2, 3, 4, 5, 6]

冒泡排序的时间复杂度分析 ：

冒泡排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以， 我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
在最坏情况下，也就是假如要排序的元素为{6,5,4,3,2,1}逆序，那么: 元素比较的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
元素交换的次数为:
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
总执行次数为:
(N^2 /2-N/2)+(N^2 /2-N/2)=N^2-N; 按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N^2).