冒泡排序(java)——3种方法

这里的冒泡是按照从小到大的顺序来的

思想：将相邻的元素两两比较， 当一个元素大于右侧相邻的元素时，交换他们的位置；当一个元素小于右侧相邻的元素时，不做任何改变。

一、第一种方法

public static void main(String[] args) {
    int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

private static void sort(int[] arr) {
    for (int i = 0; i < arr.length - 1; ++i) {
        for (int j = 0; j < arr.length - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                exchange(arr, j, j + 1);
            }
        }
    }
}
private static  void exchange(int[] nums, int i ,int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

二、第二种方法

/**
 * 冒泡排序的第二种写法
 * 在这种情况下，用一个标记来判断当前数列是否已经有序，若有序，则接下来的排序不必执行，因为已经排好序了
 */
public class BubbleSort02 {
    public static void main(String[] args) {
        int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    private static  void  sort(int[] arr) {
        //有序标记
        boolean isSwapped = true;
        for (int i = 0; i < arr.length - 1; ++i) {
            if (!isSwapped) return;
            isSwapped = false;
            for (int j = 0; j < arr.length - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    isSwapped = true;
                    exchange(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 数组中元素的交换
     */
    private static void exchange(int[] nums, int i ,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

三、第三种方法

/**
 * 冒泡排序的第三种写法
 * 1、记录最后一次元素交换的位置
 * 2、有序区的界定(无序数列的边界)
 */
public class BubbleSort05 {
    public static void main(String[] args) {
        int[] arr = new int[]{5, 8, 6, 3, 9, 2, 1, 7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        boolean isSwapped = true;
        //最后一次元素交换的位置
        int lastSwappedIndex = 0;
        //无序数列的边界，每次比较只需要比较到这里为止
        int disorderBorder = arr.length - 1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (!isSwapped) return;
            isSwapped = false;
            for (int j = 0; j < disorderBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    isSwapped = true;
                    exchange(arr, j, j + 1);
                    lastSwappedIndex = j;
                }
            }
            disorderBorder = lastSwappedIndex;
        }
    }
    private static void exchange(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}