冒泡排序从入门到放弃

冒泡排序是一种非常常见的排序算法。

它的原理就是，比较两个相邻元素的值，将大的值交换到右边。

原理很简单，现在来说说执行的思路。

第一趟比较：

首先比较第一和第二个数，将小数放在前面，将大数放在后面。比较第2和第3个数，将小数放在前面，大数放在后面。如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤直至全部排序完成。

第二趟比较：

在上面一趟比较完成后，最后一个数一定是数组中最大的一个数。所以在比较第二趟的时候，最后一个数是不用参加比较的。

在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

依次类推，每一趟比较次数减少一次。

这里我们来举一个例子。

要排序数组:[20,11,35,61,89,36,55]

第一趟排序：

第一次排序：20和11比较，20大于11，交换位置 [11,20,35,61,89,36,55]

第二次排序：20和35比较，20小于35，不交换位置　　 [11,20,35,61,89,36,55]

第三次排序：35和61比较，35小于61，不交换位置　　 [11,20,35,61,89,36,55]

第四次排序：61和89比较，61小于89，不交换位置　　 [11,20,35,61,89,36,55]

第五次排序：89和36比较，89大于36，交换位置　　　 [11,20,35,61,36,89,55]

第六次排序：89和55比较，89大于55，交换位置 [11,20,35,61,36,55,89]

第一趟总共进行了六次比较。

第二趟排序：

第一次排序：11和20比较，11小于20，不交换位置　 [11,20,35,61,36,55,89]

第二次排序：20和35比较，20小于35，不交换位置 [11,20,35,61,36,55,89]

第三次排序：35和61比较，35小于61，不交换位置 [11,20,35,61,36,55,89]

第四次排序：61和36比较，61大于36，交换位置 [11,20,35,36,61,55,89]

第五次排序：61和55比较，61大于55，交换位置 [11,20,35,36,55,61,89]

第二趟总共进行了5次比较

第三趟排序：

11和20比较，11小于20，不交换位置 [11,20,35,36,55,61,89]

第二次排序：20和35比较，20小于35，不交换位置 [11,20,35,36,55,61,89]

第三次排序：35和36比较，35小于36，不交换位置 [11,20,35,36,55,61,89]

第四次排序：36和61比较，36小于61，不交换位置 [11,20,35,36,55,61,89]

第三趟总共进行了4次比较

以此类推，最终得到下面这个结果

我们到代码中来实现一下。

第一步，我们下来实现一下比较相邻的两个元素

public class Demo1 {
    public static void main(String[] args) {
        int[] arr = {20, 11, 35, 61, 89, 36, 55};
        
        for (int i = 0; i < arr.length - 1; i++) {
            //相邻两个位置的元素进行比较
            int j = i + 1;
            //如果左边的元素大于右边则把这个元素换到右边
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

    }
}

到这里，我们可以确保一趟比较下来，最大的元素会到数组的末尾。但是我们这里只完成了一趟比较。我们需要完成多趟比较，具体多少趟取决于总共有几个元素。这里不妨使用times来表示需要完成的趟数，即

 for (int times = 1; times <= arr.length; times++) {
       //完成比较需要的代码    
 }

最好每完成一趟，我们就将数组打印一次。我们来修改代码

import java.util.Arrays;

public class Demo1 {
    public static void main(String[] args) {
        int[] arr = {20, 11, 35, 61, 89, 36, 55};
        for (int times = 1; times <= arr.length; times++) {
            System.out.print("第" + times + "趟排序: ");
            for (int i = 0; i < arr.length - 1; i++) {
                //相邻两个位置的元素进行比较
                int j = i + 1;
                //如果左边的元素大于右边则把这个元素换到右边
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            //打印数组
            System.out.println(Arrays.toString(arr));
        }
    }
}

结果如下：

第1趟排序: [11, 20, 35, 61, 36, 55, 89]
第2趟排序: [11, 20, 35, 36, 55, 61, 89]
第3趟排序: [11, 20, 35, 36, 55, 61, 89]
第4趟排序: [11, 20, 35, 36, 55, 61, 89]
第5趟排序: [11, 20, 35, 36, 55, 61, 89]
第6趟排序: [11, 20, 35, 36, 55, 61, 89]
第7趟排序: [11, 20, 35, 36, 55, 61, 89]

截个图，有图有真相