冒泡排序

一.简单的冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @Author wzy
 * @Date 2024/3/17 12:27
 * @description: 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 9, 7, 4, 1, 3, 2, 8};
        // 调用冒泡排序方法
        bubbleSort(array);
    }

    private static void bubbleSort(int[] array) {
        for (int j = 0; j < array.length - 1; j++) {
            for (int i = 0; i < array.length - 1; i++) {
                if (array[i] > array[i + 1]) {
                    // 交换元素位置
                    swap(array, i, i + 1);
                }
            }
            System.out.println("第" + (j + 1) + "轮排序后的数组：" + Arrays.toString(array));
        }
        System.out.println("排序后的数组：" + Arrays.toString(array));
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

结果：

image-20240317124436560

我们再将每一轮排序的比较次数打印出来：

image-20240317124854679

可以看见，每一轮排序都比较相同次数，这显然是多余操作的。

二.优化：减少比较次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void bubbleSort(int[] array) {
       for (int j = 0; j < array.length - 1; j++) {
           //优化 i < array.length - 1 =》i < array.length - 1 - j 减少比较次数
           for (int i = 0; i < array.length - 1 - j; i++) {
               System.out.println("比较次数：" + (i + 1));
               if (array[i] > array[i + 1]) {
                   // 交换元素位置
                   swap(array, i, i + 1);
               }
           }
           System.out.println("第" + (j + 1) + "轮排序后的数组：" + Arrays.toString(array));
       }
       System.out.println("排序后的数组：" + Arrays.toString(array));
   }

结果：

image-20240317133356658

可以看见比较次数逐次递减。

三.优化：减少冒泡次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static void bubbleSort(int[] array) {
        for (int j = 0; j < array.length - 1; j++) {
            boolean swapped = false;//是否发生了交换
            for (int i = 0; i < array.length - 1 - j; i++) {
//                System.out.println("比较次数：" + (i + 1));
                if (array[i] > array[i + 1]) {
                    // 交换元素位置
                    swap(array, i, i + 1);
                    swapped = true;//发生交换 设置为true
                }
            }
            if (!swapped) {
                // 如果一轮比较下来没有发生交换，说明数组已经有序，可以提前结束排序
                break;
            }
            System.out.println("第" + (j + 1) + "轮排序后的数组：" + Arrays.toString(array));
        }
        System.out.println("排序后的数组：" + Arrays.toString(array));
    }

结果：

image-20240317130245461

可以看见，排序次数由七次减少到5次了。

四.优化：经一步优化比较次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void bubbleSort_V2(int[] array) {
     int n = array.length - 1;//循环比较的次数
     while (true) {
         int last = 0;//最后一次交换的索引位置
         for (int i = 0; i < n; i++) {
             System.out.println("比较次数：" + (i + 1));
             if (array[i] > array[i + 1]) {
                 swap(array, i, i + 1);
                 last = i;
             }
         }
         System.out.println("排序后的数组：" + Arrays.toString(array));
         n = last;
         if (n == 0) {
             //最后一次交换的索引位置为0，说明已经排好序了，直接退出循环
             break;
         }
     }
     System.out.println("==========冒泡排序后：" + Arrays.toString(array));

 }

结果：

image-20240317132818964

对比第二种优化比较次数来看：比较次数更加减少了