冒泡排序及其优化

1.冒泡排序算法

1.1实现排序思想图

每一轮排序确定最大的那个数，temp作为中间量进行两个数据交换

冒泡排序的时间复杂度是n^2

2.冒泡排序的优化

2.1代码实现

public class Test1 {

    public static void main(String[] args) {
        int[] arr1 = {8, 4, 2, 1, 12, 23, 344};
        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        int[] arr3 = Arrays.copyOf(arr1, arr1.length);
        int len = arr1.length;

        System.out.println("--------冒泡排序优化前--------");
        int count1 = 0;
        int count4 = 0;
        for (int i = 0; i < len; i++) {

            for (int j = 0; j < len - 1 - i; j++) {
                count4 ++;
                if (arr1[j] > arr1[j + 1]) {
                    // 交换元素
                    int temp = arr1[j];
                    arr1[j] = arr1[j + 1];
                    arr1[j + 1] = temp;
                }
            }
            count1 ++;
            System.out.println("第" + (i ) + "趟排序后的数组" + Arrays.toString(arr1));
        }

        System.out.println("冒泡排序后的数组" + Arrays.toString(arr1));
        System.out.println("经历了" + count1 + "趟");
        System.out.println("比较了" + count4 + "次");

        // 冒泡排序优化：添加有序标志

        System.out.println("--------冒泡排序优化比较轮数后--------");
        int count2 = 0;
        for (int i = 0; i < len; i++) {

            // 做一个标识符，默认为false
            boolean isSorted = false;

            for (int j = 0; j < len - 1 - i; j++) {
                if (arr2[j] > arr2[j + 1]) {
                    // 交换元素
                    int temp = arr2[j];
                    arr2[j] = arr2[j + 1];
                    arr2[j + 1] = temp;

                    isSorted = true;
                }
            }

            count2 ++;
            System.out.println("第" + (i + 1) + "趟排序后的数组" + Arrays.toString(arr2));
            // 如果本轮没有交换，说明数组已经有序，直接退出
            if (!isSorted) {
                break;
            }
        }

        System.out.println("冒泡排序后的数组" + Arrays.toString(arr2));
        System.out.println("经历了" + count2 + "趟");

        System.out.println("--------冒泡排序优化比较次数后--------");
        int count3 = 0;
        int position =  len - 1;
        for (int i = 0; i < len; i++) {
            int exChange = 0;
            for (int j = 0; j < position; j++) {
                count3 ++;
                if (arr3[j] > arr3[j + 1]) {
                    int temp = arr3[j];
                    arr3[j] = arr3[j + 1];
                    arr3[j + 1] = temp;
                    exChange = j;
                }
            }
            System.out.println("第" + (i + 1) + "趟排序后的数组" + Arrays.toString(arr3));
            position = exChange;
            if (position == 0) {
                break;
            }
        }
        System.out.println("冒泡排序后的数组" + Arrays.toString(arr3));
        System.out.println("比较" + count3 + "次");
    }
}

2.2代码运行结果图

2.3结果分析

轮数优化：优化前后的比较交换轮数（交换次数也会少）

通过看是否在下一轮发生交换，如果没有发生交换，直接结束。

后续不交换，结束后交换次数也减少

次数优化：优化前后的比较交换次数（同时轮数也会少）

定义一个上次交换最后的位置，下一次就循环到那个位置即可，如果未发生改变，同样直接结束，这个更像上一次优化的继续优化。

因此轮数较少，次数也减少