[数据结构与算法]数据结构和算法（十一）排序算法之冒泡排序

1、冒泡排序基本介绍

? 冒泡排序（Bubble Sorting）是一种简单的排序算法，通过重复循环要进行排序的元素，依次比较相邻元素的值，如果发现逆序就进行交换，使值较大的元素后移。

? 排序过程中，各元素不断接近自己的位置，如果一趟比较没有进行交换，说明序列是有序的，可以在排序过程中设置一个 flag 判断元素是否进行交换。

2、冒泡排序规则

• 一共进行数组大小 - 1 次循环
• 每一趟排序的次数在逐渐减少，比较相邻元素的值，第一个比第二个大就进行交换
• 持续对越来越少的元素进行比较，直到没有任何元素需要进行比较
• 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序

3、冒泡排序代码示例

// 排序规则：从第一个下标位置开始，对相邻元素的值依次进行比较，大的值后移一位继续比较，直到比后一位元素小为止
int arr[] = {2,4,6,1,5,8, -3}; // 原始数组数据
int temp = 0;
// 进行一次排序，第一次排序，将数组内最大的数排在最后
for (int i = 0; i < arr.length - 1; i++) {
    // 前后相邻位置数进行比较，如果前面的数比后面的数大，进行交换
    if (arr[i] > arr[i + 1]) {
        temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
    }
}

冒泡排序具体实现：每次循环次数 arr.length - 1;

public static void main(String[] args) {
    int arr[] = {2,-1,6,1,5,8, -3}; // 原始数组数据
    int temp = 0;
    // 冒泡排序的时间复杂度为 O(n^2)
    // 外层循环控制遍历次数
    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]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

原来顺序就是正常，或者一部分已经排好序了，可以通过标识符 flag 判断

public static void main(String[] args) {
    int arr[] = {2,-1,6,1,5,8, -3}; // 原始数组数据
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}
// 冒泡排序
public static void bubbleSort(int[] arr) {
    int temp = 0;
    boolean flag = false;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 通过标识符判断在排序中有没有进行过交换
        if (!flag) { // 进行过交换继续下一次
            break;
        } else { // 没有进行过交换，序列有序
            flag = false;
        }
    }
}