【经典算法】冒泡排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了【经典算法】冒泡排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

一、冒泡排序的基本思想

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

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

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

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

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

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

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

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

冒泡排序法的基本思路,Java,数据结构与算法,数据结构,排序算法,算法,Powered by 金山文档

第一次循环：

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;
            }
        }
    }
}

运行结果：文章来源地址https://www.toymoban.com/news/detail-795890.html