冒泡排序算法

????????冒泡排序，也称为Bubble Sort，是一种简单的计算机科学排序算法。该算法重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。这个过程会不断重复，直到没有再需要交换的相邻元素为止，也就是说该数列已经排序完成。

????????冒泡排序的名字来源于越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

????????冒泡排序的基本思想是通过对待排序序列从前向后（从下标较小的元素开始），依次对相邻两个元素的值进行两两比较，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒出。例如，对于一个待排序数组：3，9，-1，10，20，第一轮排序后，将最大的元素20固定到了最后的位置；然后在第二轮排序时，因为20的位置已经固定，所以只对前4个进行排序即可。

优化：

? ? ? ? 因为排序的过程中，个元素不断接近自己的位置，如果一次比较下来没有进行交换过，说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行交换过。从而减少不必要的比较。

推敲冒泡排序中：?

public class Sort {
    public static void main(String[] args) {
        //原始的冒泡排序
        int arr[] = {3, 9, -1, 10, -2};
        System.out.println("====排序前====");
        System.out.println("第0轮：" + Arrays.toString(arr));

        System.out.println("===开始排序===");
        int temp;
        for (int j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第1轮：" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第2轮：" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 2; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第3轮：" + Arrays.toString(arr));

        for (int j = 0; j < arr.length - 1 - 3; j++) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.println("第4轮：" + Arrays.toString(arr));
    }
}

?

?传统的冒泡排序：

public class BubbleSort {
    public static void main(String[] args) {
        int[] arrays = {12, 5, 8, 9, 4, 2};
        System.out.println("===排序之前的数据===");
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "\t");
        }
        System.out.println();

        //排序操作
        int temp = 0;
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j + 1] < arrays[j]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
        System.out.println("===排序之后的数据===");
        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "\t");
        }
        System.out.println();
    }
}

优化之后的冒泡排序：

优化的内容，只是检验该数组是否具备提前结束的必要，如果数组在每次排序后都需要进行交换，其运行的时间效率并不能提高。

public class BubbleSortUpdate {
    public static void main(String[] args) {
        int[] arrays = {5, 2, 8, 9, 4, 12};
        System.out.println("排序前：" + Arrays.toString(arrays));
        boolean flag = false;
        int temp = 0;
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - i - 1; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    flag = true;
                    //代表在一次排序中，进行交换过，如果交换过，说明排序还未结束，下次接着进行排序
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
            if (!flag) { //在一次排序中，一次都没有进行交换
                break;
            } else {
                flag = false; //重置flag，进行下次判断
            }
            System.out.println("轮数" + (i + 1) + " :" + Arrays.toString(arrays));
        }
        System.out.println("排序后：" + Arrays.toString(arrays));
    }
}

?