冒泡算法-Buddle Sort

1.原理

每次比较两个相邻的元素，如果前一个比后一个大，就交换彼此的位置。

2.图解

image.png

3.文字描述过程

对于一组包含n个元素的记录，最坏的情况需要进行n-1趟排序。

• 第1趟：依次比较下标0和1，1和2，...(n-2)和(n-1)的元素，如果发现前一项大于后一项，交换彼此的位置，经过一趟排序后，最大的元素排在最后面
• 第2趟：依次比较下标0和1，1和2，...(n-3)和(n-2)和元素，经过前后比较，最大的元素排在倒数第二的位置
• 进行n-1趟：比较下标0和1的元素，如果下标为0的元素大于下标为1的元素，交换位置，排序结束

4.Java代码实现

public static void main(String[] args) {
        int[] arr = {3, 5, 1, 8, 6};
        bubbleSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void bubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

5.复杂度分析

• 时间复杂度
• 空间复杂度
• 稳定性

6.优化

在上面的代码里，即使经过几趟排序之后元素是有序了，也会经过n-1趟排序，只比较不交换罢了，优化：当某趟没有发生交换，说明数组已经有序，就中断遍历。

public static void bubbleSort(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            boolean isSwapped = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                    isSwapped = true;
                }
            }
            if (!isSwapped) {
                break;
            }
        }
    }