05、数据结构与算法 - 实战：排序算法之冒泡排序

1、基本思想

通过对待排序序列从前向后，依此比较相邻元素的值，若发现逆序，则使较大的元素逐渐向后移，就像水底下的气泡一样逐渐往上冒。当一轮排序下来没有元素交换过，则说明序列有序了。

2、图解

3、代码实现

package cn.klb.datastructures.sort;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 实现对数组的冒泡排序
 * @Date: Create in 2023/4/3 21:04
 * @Modified By:
 */
public class Bubble {
   
     

    public static void sort(int[] arr) {
   
     
        int temp = 0;   // 临时变量，用于交换数据
        boolean flag = false;    // 一轮走完后数组是否进行了交换
        // 进行 arr.length - 1 轮循环，减一是因为最后一个数字的后面没有数字
        for (int i = 0; i < arr.length - 1; i++) {
   
     
            // 第i轮进行arr.length - 1 - i次比较
            // -i是因为最大的数字已经排序好了，不用比较
            for (int j = 0; j < arr.length - 1 - i; j++) {
   
     
                // 如果当前数字比后一位数字大，则交换顺序
                if (arr[j] > arr[j + 1]) {
   
     
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;    // 如果本轮进行交换，则flag=true
                }
            }

            if (flag) {
   
     
                flag = false;   // 重置flag
            } else {
   
         // 如果本轮没有交换，则说明数组已经有序，提前结束
                break;
            }
        }
    }
}

4、时间复杂度

总结冒泡排序的步骤，核心步骤为比较和交换，假设比较次数为C，交换次数为S。
最好的情况下：序列本身已经是从小到大有序，这时只需要1轮循环，因此，C=n-1=O(n)，S=0=O(1)；如果没有提前退出这个优化操作，那么两层for循环会老老实实跑完，这时候C=n(n-1)/2=O(n²)，S=0=O(1)。
最坏的情况下：序列完全是从大到小的，这时需要循环n-1轮，第一轮、第二轮…分别进行n-1次比较和n-1次交换、n-2次比较和n-2次交换…，因此，C=n(n-1)/2=O(n²)，S=3n(n-1)/2=O(n²)。交换操作需要最少三步，所以前面有个系数3。
一般我们讨论时间复杂度都是讨论最差的情况，而且哪怕不交换也得是先比较过后才确定交不交换，所以冒泡排序的时间复杂度为0(n²)。

5、稳定性

通过代码可以分析，如果存在两个数是相同的且挨着，不会满足第二层for循环里面的if判断，因此相同数字不会发生交换，即两个相同数字的前后关系不会发生改变，也就是说冒泡排序是稳定的。

6、测试

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.sort.*;
import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 排序测试
 * @Date: Create in 2023/4/3 21:32
 * @Modified By:
 */
public class SotrTest {
   
     

    @Test
    public void testBubble() {
   
     
        int[] arr = new int[8];
        for (int i = 0; i < 8; i++) {
   
     
            arr[i] = (int) (Math.random() * 800000);
        }
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = new Date();
        System.out.println("-----" + sdf.format(date1) + "-----");
        //System.out.println(Arrays.toString(arr));

        Bubble.sort(arr);

        Date date2 = new Date();
        System.out.println("-----" + sdf.format(date2) + "-----");
        //System.out.println(Arrays.toString(arr));
        // 8万的随机数据进行冒泡排序，我的电脑花了大约10秒
        // 80万的随机数据进行冒泡排序，我的电脑花了大约20分24秒(好慢的感觉)
    }
}