排序算法之冒泡排序

一、简介

稳定：如果A原本在B前面，而A=B，排序之后A仍然在B的前面；
不稳定：如果A原本在B的前面，而A=B，排序之后A可能会出现在B的后面；
时间复杂度： 描述一个算法执行所耗费的时间；
空间复杂度：描述一个算法执行所需内存的大小；
n：数据规模；
k：“桶”的个数；
In-place：占用常数内存，不占用额外内存；
Out-place：占用额外内存。

算法步驟：

比较相邻的元素，如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的比较，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；
重复步骤1~3，直到排序完成。

二、代码实现

public class BubbleSort {

    /**
     * flag的作用：flag是对冒泡排序算法的优化，每次内循环结束都会将长度为N-i-1数组中最大的元素交换到最后面，
     * 当内循环结束没有发生数据的交换，说明数组已经是有序的了，此时flag=false，退出循环。
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    public static void bubbleSortBack(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {12, 11, 15, 50, 7, 65, 3, 99};
        System.out.println("---排序前:  " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("从小到大排序后:  " + Arrays.toString(arr));
        bubbleSortBack(arr);
        System.out.println("从大到小排序后:  " + Arrays.toString(arr));
    }
}

三、应用场景

冒泡排序在实际工程中使用较少，但在教学、学习和特定场景下仍然具有一定的应用价值。对于大规模数据集的排序，通常会选择更高效的排序算法，如快速排序、归并排序等。

参考链接：
十大经典排序算法（Java实现）