open  API 生成的冒泡排序及优化方案

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static void bubbleSort(int[] arr) {
        int temp;
        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;
                }
            }
        }
    }
}

//添加标记优化，一种优化方法是添加一个标记，记录每一轮是否进行了交换
//如果没有进行交换，则说明已经排好序，可以直接结束排序。这样可以避免不必要的比较和交换，提高排序效率。
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static void bubbleSort(int[] arr) {
        int temp;
        boolean flag = true; // 添加标记
        for (int i = 0; i < arr.length - 1 && flag; i++) {
            flag = false;
            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; // 发生了交换
                }
            }
        }
    }
}

//每轮排序中记录最后一次交换的位置
//该位置之后的元素已经有序，下一轮排序时只需要比较到该位置即可。这样可以进一步减少比较和交换的次数，提高排序效率。
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static void bubbleSort(int[] arr) {
        int temp;
        int lastExchangeIndex = 0; // 记录最后一次交换的位置
        int sortBorder = arr.length - 1; // 无序数列的边界
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (flag) {
                break;
            }
        }
    }
}
//鸡尾酒排序(双向冒泡排序)
//鸡尾酒排序先从左到右进行冒泡排序，然后再从右到左进行冒泡排序，如此交替进行，可以让排序更快地逼近最终状态
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        cocktailSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
    public static void cocktailSort(int[] arr) {
        int temp;
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            for (int i = left; i < right; i++) { // 从左到右冒泡
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            right--;
            for (int i = right; i > left; i--) { // 从右到左冒泡
                if (arr[i] < arr[i - 1]) {
                    temp = arr[i];
                    arr[i] = arr[i - 1];
                    arr[i - 1] = temp;
                }
            }
            left++;
        }
    }
}