14、排序算法-冒泡排序

来源：https://www.bilibili.com/video/BV1B4411H76f?p=39

一、思路

冒泡排序：从下标较小的元素开始比较，比的是相邻的元素，逆序则交换

如果想从小到大排列，这样一趟比较下来，最后一个就是最大的

例如：[3,9，-1，10，-2]

第一趟：

• 比较3和9，由小到大，不换，[3,9，-1，10，-2]
• 比较9和-1，逆序，换，[3,-1，9，10，-2]
• 比较9和10，不换，[3,-1，9，10，-2]
• 比较10和-2，换，[3,-1，9，-2，10]

第二趟：

• 比较3和-1，换，[-1,3，9，-2，10]
• 比较3和9，不换，[-1,3，9，-2，10]
• 比较9和-2，换，[-1,3，-2，9，10]
• 比较9和10，不换，[-1,3，-2，9，10] （这个可以不用比，最后已经是最大的了）

第三趟：

• 比较-1和3，不换，[-1,3，-2，9，10] 
• 比较3和-2，换，[-1,-2，3，9，10]（后面不用比了，已经最大）

第四趟：

• 比较-1和-2，换，[-2,-1，3，9，10]（后面不用比了，已经最大）

二、实现

//冒泡排序
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {3,9,-1,10,-2};
        System.out.println(Arrays.toString(arr));

        bubbleSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

}

结果

[3, 9, -1, 10, -2]
[-2, -1, 3, 9, 10]

中间用Arrays.toString()方法时出现了点问题，之前一直是自己重写的toString方法，然后直接arr.toString()了，显然是不行的，得记住这个失误。

当然，程序还可以优化一下，加一个标志位，默认为false，一旦运行进入if判断，将其置为true，表明本次进行了交换，在i循环中加入一个判断，如果某一次运行完成没有进行交换，说明已经排序完成了，这样在数据量大的情况下可以节省很长时间。

    public static void bubbleSort(int[] arr){
        //默认本次没有进行交换
        boolean flag = false;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]){
                    flag = true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if(!flag){
                //flag = false，确实没交换，已经排序完成了
                break;
            }else {
                flag = false;
            }
        }
    }