【经典算法】冒泡排序

向右看齐 2023-09-30 18:41 7阅读 0赞

冒泡排序是Java中非常经典的一种排序方法，可以将多个数字进行升序排序，效率比较高。

--------------------

### 一、冒泡排序的基本思想 ###

冒泡排序(Bubble Sorting)的基本思想是: 通过对待排序序列从前向后(从下标较小的元素开始),**依次比较相邻元素的值，若发现逆序则交换**，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

**冒泡排序算法的运作如下：**

1、比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array\[length - 1\]。

2、第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。

3、持续每次对越来越少的元素重复上面的步骤，**直到没有任何一对数字需要比较。**

### 二、冒泡排序的原理（图解） ###

冒泡排序的原理是：外层循环遍历整个数组，内层循环对相邻元素进行比较，把最大值选出来交给外层下标，依次进行。

定义的数组int arr\[\] = \{15, 63, 97, 12, 235, 66\}

![978e321900a3886ac99dca96b20e57a4.png][]

**第一次循环：**

1、首先比较arr\[0\]和arr\[1\]，即15和63；因为15< 63，因此两个数的位置不变。

**\[15, 63, 97, 12, 235, 66\]**

比较和交换对应的代码如下：

if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
    }

2、接着比较arr\[1\]和arr\[2\]，即63和97；因为63 < 97，因此两个数的位置不变,如下

**\[15, 63, 97, 12, 235, 66\]**

3、接着比较arr\[2\]和arr\[3\]，即97和12；因为97 > 12，因此交换两个数的位置，交换完的数组如下：

**\[15, 63, 12, 97, 235, 66\]**

4、接着比较arr\[3\]和arr\[4\]，即97和235；因为97 < 235，因此两个数的位置不变，如下：

**\[15, 63, 12, 97, 235, 66\]**

5、最后比较arr\[4\]和arr\[5\]，即235和66；因为235 > 66，因此交换两个数的位置,交换完的数组如下:

**\[15, 63, 12, 97, 66, 235\]**

至此第一次循环结束，由于是相邻两数比较，可以看到第一次循环我们只需要进行5次比较，即：(arr.length - 1) 次。

接着下一轮，不断循环

用具体的例子展示，每次循环需要比较的次数如下：

第一次循环：arr.length - 1 - 0
    第二次循环：arr.length - 1 - 1
    第三次循环：arr.length - 1 - 2
    ...

### **三、时间复杂度** ###

在通常情况下。冒泡排序的比较次数 = (n - 1) + (n - 2) + ... + 2 + 1，即：n \* (n - 1) / 2，所以冒泡排序的**时间复杂度为：O(n^2)。**

### **四、使用场景** ###

由于冒泡排序的时间复杂度为：O(n^2)。因此，在进行量比较大的排序时，最好不要采用冒泡排序。经过简单的测试，在1000个数字以内的排序，用冒泡排序是可以接受的。1000个随机数使用冒泡排序耗时一般在5毫秒以内，但是当数字个数达到10000个时，耗时会达到100+毫秒，简直是灾难。

### **五、最优情况** ###

对排序算法熟悉的人应该知道，冒泡排序最优情况的时间复杂度是：O(n)，怎么得出来的了？通过上文的代码是无法达到O(n)的，需要对上文的代码进行一点点的优化，优化后的代码如下。

public static void bubbleSort(int[] arr) {
            // 临时变量
            int temp = 0;
            // 标识变量，表示是否进行过交换
            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;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                System.out.println("第" + (i + 1) + "趟排序后的数组");
                System.out.println(Arrays.toString(arr));
                // 在一趟排序中，一次交换都没有发生过
                if (!flag) {
                    break;
                } else {
                    // 重置flag, 进行下次判断
                    flag = false;
                }
            }
        }

### 六、完整代码 ###

package com.example.demo;
    
    import java.text.SimpleDateFormat;
    import java.util.Arrays;
    import java.util.Date;
    
    /**
     * @author Biyu
     * @projectName demo
     * @className: BubbleSort
     * @description //TODO
     * @date: 2023-01-10 22:44
     */
    public class BubbleSort {
    
        public static void main(String[] args) {
            int arr[] = {15, 63, 97, 12, 235, 66};
    
            Date beginDate = new Date();
            SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
            String beginDateStr = simpleDateFormat.format(beginDate);
            System.out.println("排序前的时间是=" + beginDateStr);
    
            bubbleSort(arr);
    
            Date endDate = new Date();
            String endDateStr = simpleDateFormat.format(endDate);
            System.out.println("排序后的时间是=" + endDateStr);
        }
    
        /**
         * 冒泡排序
         *
         * @param arr
         */
        public static void bubbleSort(int[] arr) {
            // 临时变量
            int temp = 0;
            // 标识变量，表示是否进行过交换
            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;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                System.out.println("第" + (i + 1) + "趟排序后的数组");
                System.out.println(Arrays.toString(arr));
                // 在一趟排序中，一次交换都没有发生过
                if (!flag) {
                    break;
                } else {
                    // 重置flag, 进行下次判断
                    flag = false;
                }
            }
        }
    }

运行结果：

![689e7b211d4dab49ea95640017ac18b2.png][]

[978e321900a3886ac99dca96b20e57a4.png]: https://img-blog.csdnimg.cn/img_convert/978e321900a3886ac99dca96b20e57a4.png
[689e7b211d4dab49ea95640017ac18b2.png]: https://img-blog.csdnimg.cn/img_convert/689e7b211d4dab49ea95640017ac18b2.png