排序算法-冒泡排序

基本思路

遍历给定的数组，从左往右，两两比较，小的放在左边，大的放在右边，遍历完成，数组有序。

先来看一个冒泡排序的过程：

给定数组：[5,3,2,1,4]

排序结果：[1,2,3,4,5]

拆解步骤

1.第一轮从左往右循环，遍历前5个数：

(1) 来到5和3，5大于3  ==>  5和3交换 

 

(2) 来到5和2，5大于2 ==> 5和2交换

 (3) 来到5和1,5大于1 ==> 5和1交换

 (4) 来到5和4,5大于4 ==> 5和4交换

 第一轮遍历结束，最右侧的5是数组中最大的，不用动了。

 

2.第二轮从左往右循环，遍历前4个数

 (1) 来到3和2，3大于2 ==> 3和2交换

(2) 来到3和1，3大于1 ==> 3和1做交换 

 

 (3) 来到3和4，3小于4 ==> 不用交换

第二轮遍历结束，最右侧的4已经是待排序数中最大的，不用动。

……略

得出规律

依次类推，得出规律：

1.每一次遍历的都是左侧待排序的数，遍历完成后会将最大的数放到最右边。

2.一共需要数组长度次数的遍历，比如数组长度是5，就需要5次遍历。

代码实现

public class BubbleSort {
 
    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 1, 4};
        for (int i : arr) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();
        bubbleSort(arr);
        System.out.println("冒泡排序后 ---->");
        for (int i : arr) {
            System.out.print(i);
            System.out.print(" ");
        }
    }
 
    /**
     * 冒泡排序
     *
     * @param arr 待排序的数组
     */
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {  // 数组长度是多少，就需要遍历多少次数组
            for (int j = 0; j < arr.length - i - 1; j++) { // 每次遍历的范围是 0 ~ len-i-1
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
 
    /**
     * 数组交换
     *
     * @param arr    数组
     * @param index1 下标1
     * @param index2 下标2
     */
    public static void swap(int[] arr, int index1, int index2) {
        arr[index1] = arr[index1] + arr[index2];
        arr[index2] = arr[index1] - arr[index2];
        arr[index1] = arr[index1] - arr[index2];
    }
}

对数器验证

import cn.hutool.core.util.RandomUtil;
import java.util.Arrays;
public class BubbleSortTest {
 
    public static void main(String[] args) {
        int[] arr1 = new int[1000];
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = RandomUtil.randomInt(0, 10000);
        }
        final int[] arr2 = Arrays.copyOf(arr1, arr1.length);
        System.out.println("拷贝的数组arr2是否等于arr1：" + equals(arr1, arr2));
        print(arr1);
        Arrays.sort(arr1);
        System.out.println("使用系统的排序算法排序后的数组 ------->");
        print(arr1);
        BubbleSort.bubbleSort(arr2);
        System.out.println("使用冒泡排序算法排序后的数组 ------->");
        print(arr2);
        System.out.println("冒泡排序算法结果与系统内置排序算法结果是否一致：" + equals(arr1, arr2));
    }
 
    public static void print(int[] arr){
        for (int i : arr) {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();
    }
 
    public static boolean equals(int[] arr1, int[] arr2){
        if(arr1 == null && arr2 == null){
            return true;
        }
        if(arr1 == null || arr2 == null){
            return false;
        }
        if(arr1.length != arr2.length){
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }
 
}

 优化

思路：如果在一次遍历中，发现所有的元素都不需要交换，那么说明这个数组已经是有序数组了。

比如一个数组：[1,2,3,4,5]，其冒泡排序过程如下：

 

 对于这种有序数组，其实只需要遍历一次就可以了。我们可以在每次循环的时候记录当前循环是否发生了交换操作，如果没有发生，就提前结束排序操作，因为数组已经是有序了。

需要优化的核心代码：

/**
 * 冒泡排序
 *
 * @param arr 待排序的数组
 */
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int i = 0; i < arr.length; i++) {  // 数组长度是多少，就需要遍历多少次数组
        boolean swaped = false; // 用来记录是否交换的变量
        for (int j = 0; j < arr.length - i - 1; j++) { // 每次遍历的范围是 0 ~ len-i-1
            if (arr[j] > arr[j + 1]) {
                swaped = true; // 如果发生了交换，就记为true
                swap(arr, j, j + 1);
            }
        }
        if(!swaped){
            // 如果一次交换都没有发生，就是数组已经有序了
            return;
        }
    }
}

其他定论

1.冒泡排序在排序期间没有申请其他的内存空间，它的空间复杂度是O(1)，所以是原地排序算法。

2.冒泡排序对于相同数值的元素来说，每次排序后所在的位置不变，因此冒泡排序是稳定的排序算法。

3.冒泡排序的时间复杂度是O(n^2)